breadth first search c program traverse graph
Dieses Tutorial behandelt die erste Breitensuche in C ++, in der der Graph oder Baum in der Breite durchlaufen wird. Sie lernen auch den BFS-Algorithmus und die Implementierung kennen:
Dieses explizite C ++ - Tutorial enthält eine detaillierte Erläuterung der Durchquerungstechniken, die für einen Baum oder eine Grafik ausgeführt werden können.
Traversal ist die Technik, mit der wir jeden einzelnen Knoten des Graphen oder eines Baums besuchen. Es gibt zwei Standardmethoden für das Durchlaufen.
- Breitensuche (BFS)
- Tiefensuche (DFS)
=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.
beste Dateiwiederherstellungssoftware Windows 10
Was du lernen wirst:
BFS-Technik (Breadth First Search) in C ++
In diesem Tutorial werden wir die Breitensuchtechnik ausführlich diskutieren.
Bei der Technik der ersten Durchquerung der Breite wird der Graph oder Baum breit in der Breite durchlaufen. Diese Technik verwendet die Warteschlangendatenstruktur, um die Scheitelpunkte oder Knoten zu speichern und um zu bestimmen, welcher Scheitelpunkt / Knoten als nächstes aufgenommen werden soll.
Der Breitengrad-Algorithmus beginnt mit dem Wurzelknoten und durchläuft dann alle benachbarten Knoten. Anschließend wird der nächste Knoten ausgewählt und alle anderen nicht besuchten Knoten untersucht. Dieser Vorgang wird wiederholt, bis alle Knoten im Diagramm untersucht sind.
Breitensuchalgorithmus
Nachstehend ist der Algorithmus für die BFS-Technik angegeben.
Betrachten Sie G als einen Graphen, den wir mit dem BFS-Algorithmus durchlaufen werden.
Sei S der Wurzel- / Startknoten des Graphen.
- Schritt 1: Beginnen Sie mit Knoten S und stellen Sie ihn in die Warteschlange.
- Schritt 2: Wiederholen Sie die folgenden Schritte für alle Knoten im Diagramm.
- Schritt 3: S in die Warteschlange stellen und verarbeiten.
- Schritt 4: Alle benachbarten Knoten von S in die Warteschlange stellen und verarbeiten.
- (ENDE DER SCHLEIFE)
- Schritt 6: AUSFAHRT
Pseudocode
Der Pseudocode für die BFS-Technik ist unten angegeben.
Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. endDurchquerungen mit Abbildungen
Sei 0 der Startknoten oder Quellknoten. Zuerst stellen wir es in die besuchte Warteschlange und alle angrenzenden Knoten in die Warteschlange.
Als nächstes nehmen wir einen der benachbarten Knoten zur Verarbeitung, d. H. 1. Wir markieren ihn als besucht, indem wir ihn aus der Warteschlange entfernen und seine benachbarten Knoten in die Warteschlange stellen (2 und 3 bereits in der Warteschlange). Da 0 bereits besucht ist, ignorieren wir es.
Zählt die Stringlänge Leerzeichen in Java?
Als nächstes entfernen wir Knoten 2 und markieren ihn als besucht. Dann wird sein benachbarter Knoten 4 zur Warteschlange hinzugefügt.
Als nächstes entfernen wir 3 aus der Warteschlange und markieren sie als besucht. Knoten 3 hat nur einen benachbarten Knoten, d. H. 0, der bereits besucht ist. Daher ignorieren wir es.
Zu diesem Zeitpunkt ist nur der Knoten 4 in der Warteschlange vorhanden. Sein benachbarter Knoten 2 ist bereits besucht, daher ignorieren wir ihn. Jetzt markieren wir 4 als besucht.
Als nächstes ist die in der besuchten Liste vorhandene Sequenz die breiteste Durchquerung des gegebenen Graphen.
Wenn wir den gegebenen Graphen und die Durchlaufsequenz beobachten, können wir feststellen, dass wir für den BFS-Algorithmus den Graphen tatsächlich in der Breite durchlaufen und dann zur nächsten Ebene übergehen.
BFS-Implementierung
#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '< Ausgabe:
Hash-Tabelle C ++ Beispiel
Breitendurchquerung für den angegebenen Graphen (mit 0 als Startknoten):
0 1 2 3 4
Wir haben das BFS im obigen Programm implementiert. Beachten Sie, dass das Diagramm die Form einer Adjazenzliste hat. Anschließend verwenden wir einen Iterator, um die Liste zu durchlaufen und BFS durchzuführen.
Wir haben das gleiche Diagramm verwendet, das wir zu Illustrationszwecken als Eingabe für das Programm verwendet haben, um die Durchlaufsequenz zu vergleichen.
Laufzeitanalyse
Wenn V die Anzahl der Eckpunkte und E die Anzahl der Kanten eines Graphen ist, kann die zeitliche Komplexität für BFS ausgedrückt werden als O (| V | + | E |) . Dies hängt jedoch auch von der Datenstruktur ab, die wir zur Darstellung des Diagramms verwenden.
Wenn wir die Adjazenzliste verwenden (wie in unserer Implementierung), ist die zeitliche Komplexität O (| V | + | E |).
Wenn wir die Adjazenzmatrix verwenden, ist die zeitliche Komplexität O (V ^ 2) .
Neben den verwendeten Datenstrukturen gibt es auch einen Faktor dafür, ob der Graph dicht oder dünn besiedelt ist.
Wenn die Anzahl der Scheitelpunkte die Anzahl der Kanten überschreitet, wird der Graph als spärlich verbunden bezeichnet, da es viele getrennte Scheitelpunkte gibt. In diesem Fall beträgt die zeitliche Komplexität des Graphen O (V).
Andererseits kann der Graph manchmal eine höhere Anzahl von Kanten als die Anzahl von Eckpunkten haben. In einem solchen Fall soll der Graph dicht besiedelt sein. Die zeitliche Komplexität eines solchen Graphen ist O (E).
Zusammenfassend lässt sich sagen, dass der Ausdruck O (| V | + | E |) davon abhängt, ob der Graph dicht oder dünn besiedelt ist. Der dominierende Faktor, d. H. Kanten oder Eckpunkte, bestimmt die zeitliche Komplexität des Graphen entsprechend.
Anwendungen von BFS Traversal
- Müllabfuhr: Die Garbage Collection-Technik, 'Cheneys Algorithmus', verwendet die Breitengrad-Durchquerung zum Kopieren der Garbage Collection.
- Rundfunk in Netzwerken: Ein Paket wandert mithilfe der BFS-Technik im Rundfunknetz von einem Knoten zum anderen, um alle Knoten zu erreichen.
- GPS Navigation: Wir können BFS in der GPS-Navigation verwenden, um alle benachbarten oder benachbarten Standortknoten zu finden.
- Websites für soziale Netzwerke: Bei einer Person 'P' können wir alle Personen in einer Entfernung finden, 'd' von p mit BFS bis zu den d-Ebenen.
- Peer-to-Peer-Netzwerke: Wiederum kann BFS in Peer-to-Peer-Netzwerken verwendet werden, um alle benachbarten Knoten zu finden.
- Kürzester Pfad und minimaler Spanning Tree im ungewichteten Diagramm: Die BFS-Technik wird verwendet, um den kürzesten Pfad zu finden, d. H. Den Pfad mit der geringsten Anzahl von Kanten in dem ungewichteten Graphen. In ähnlicher Weise können wir im ungewichteten Diagramm auch einen minimalen Spannbaum mit BFS finden.
Fazit
Die Breitensuchtechnik ist eine Methode, mit der alle Knoten eines Graphen oder eines Baums in der Breite durchlaufen werden.
Diese Technik wird meistens verwendet, um den kürzesten Weg zwischen den Knoten eines Graphen oder in Anwendungen zu finden, bei denen wir jeden benachbarten Knoten wie in Netzwerken besuchen müssen.
=> Klicken Sie hier für den kostenlosen C ++ - Kurs.
Literatur-Empfehlungen
- Binärer Suchbaum C ++: BST-Implementierung und Operationen mit Beispielen
- B-Baum- und B + -Baum-Datenstruktur in C ++
- Diagrammimplementierung in C ++ unter Verwendung der Adjazenzliste
- Datenstruktur des Binärbaums in C ++
- 12 besten Tools zur Erstellung von Liniendiagrammen zum Erstellen atemberaubender Liniendiagramme (2021 RANGLISTE)
- AVL-Baum- und Heap-Datenstruktur in C ++
- Bäume in C ++: Grundlegende Terminologie, Traversal-Techniken und C ++ - Baumtypen
- Ursache-Wirkungs-Diagramm - Dynamische Testfallschreibtechnik für maximale Abdeckung mit weniger Testfällen