Menü

DFS-C ++ - Programm (Depth First Search) zum Durchlaufen eines Diagramms oder Baums

  • Haupt
  • Andere
  • DFS-C ++ - Programm (Depth First Search) zum Durchlaufen eines Diagramms oder Baums

depth first search c program traverse graph

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Dieses Tutorial behandelt die Tiefensuche (DFS) in C ++, in der ein Diagramm oder ein Baum in der Tiefe durchlaufen wird. Sie lernen auch den DFS-Algorithmus und die Implementierung kennen:

Die Tiefensuche (DFS) ist eine weitere Technik, mit der ein Baum oder ein Diagramm durchlaufen wird.

DFS beginnt mit einem Wurzelknoten oder einem Startknoten und untersucht dann die benachbarten Knoten des aktuellen Knotens, indem es tiefer in das Diagramm oder einen Baum eintaucht. Dies bedeutet, dass in DFS die Knoten eingehend untersucht werden, bis ein Knoten ohne untergeordnete Knoten gefunden wird.

Sobald der Blattknoten erreicht ist, zieht sich DFS zurück und beginnt auf ähnliche Weise, weitere Knoten zu erkunden.

=> Sehen Sie sich hier den C ++ - Schulungsleitfaden für Anfänger an.

Tiefensuche

Was du lernen wirst:

Tiefensuche (DFS) in C ++

Im Gegensatz zu BFS, bei dem wir die Knoten in der Breite untersuchen, untersuchen wir in DFS die Knoten in der Tiefe. In DFS verwenden wir eine Stapeldatenstruktur zum Speichern der zu untersuchenden Knoten. Die Kanten, die uns zu unerforschten Knoten führen, werden als 'Erkennungskanten' bezeichnet, während die Kanten, die zu bereits besuchten Knoten führen, als 'Blockkanten' bezeichnet werden.

Als nächstes sehen wir den Algorithmus und den Pseudocode für die DFS-Technik.

DFS-Algorithmus

  • Schritt 1: Fügen Sie den Wurzelknoten oder Startknoten eines Baums oder einer Grafik in den Stapel ein.
  • Schritt 2: Nehmen Sie das oberste Element vom Stapel und fügen Sie es der besuchten Liste hinzu.
  • Schritt 3: Suchen Sie alle benachbarten Knoten des als besucht gekennzeichneten Knotens und fügen Sie die noch nicht besuchten Knoten zum Stapel hinzu.
  • Schritt 4 : Wiederholen Sie die Schritte 2 und 3, bis der Stapel leer ist.

Pseudocode

Der Pseudocode für DFS ist unten angegeben.

Der Pseudocode für DFS

Aus dem obigen Pseudocode geht hervor, dass der DFS-Algorithmus auf jedem Scheitelpunkt rekursiv aufgerufen wird, um sicherzustellen, dass alle Scheitelpunkte besucht werden.

Durchquerungen mit Abbildungen

Lassen Sie uns nun die DFS-Durchquerung eines Graphen veranschaulichen. Aus Gründen der Übersichtlichkeit verwenden wir dasselbe Diagramm, das wir in der BFS-Abbildung verwendet haben.

DFS-Abbildungen mit Durchquerungen

Sei 0 der Startknoten oder Quellknoten. Zuerst markieren wir es als besucht und fügen es der besuchten Liste hinzu. Dann schieben wir alle benachbarten Knoten in den Stapel.

Schieben Sie alle benachbarten Knoten in den Stapel

Als nächstes nehmen wir einen der benachbarten Knoten, um ihn zu verarbeiten, d. H. Die Spitze des Stapels, die 1 ist. Wir markieren ihn als besucht, indem wir ihn der besuchten Liste hinzufügen. Suchen Sie nun nach den benachbarten Knoten von 1. Da 0 bereits in der besuchten Liste enthalten ist, ignorieren wir diese und besuchen 2, die die Spitze des Stapels darstellt.

DFS-Abbildung - Schritt 3

Als nächstes markieren wir Knoten 2 als besucht. Sein benachbarter Knoten 4 wird dem Stapel hinzugefügt.

DFS-Illustration Schritt 4

Als nächstes markieren wir 4, die als Besuch die Spitze des Stapels darstellt. Knoten 4 hat nur Knoten 2 als seinen Nachbarn, der bereits besucht ist, daher ignorieren wir ihn.

DFS-Illustration Schritt 5

Zu diesem Zeitpunkt ist nur der Knoten 3 im Stapel vorhanden. Sein benachbarter Knoten 0 ist bereits besucht, daher ignorieren wir ihn. Jetzt markieren wir 3 als besucht.

DFS-Illustration Schritt 6

Jetzt ist der Stapel leer und die besuchte Liste zeigt die Reihenfolge der Tiefenüberquerung des angegebenen Graphen.

Wenn wir den gegebenen Graphen und die Durchlaufsequenz beobachten, stellen wir fest, dass wir für den DFS-Algorithmus den Graphen tatsächlich in der Tiefe durchlaufen und ihn dann erneut zurückverfolgen, um neue Knoten zu erkunden.

Implementierung der Tiefensuche

Implementieren wir die DFS-Traversal-Technik mit C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Ausgabe:

Tiefendurchquerung für das gegebene Diagramm:

0 1 2 4 3

Wir haben das Diagramm in dem Programm, das wir zur Veranschaulichung verwendet haben, erneut verwendet. Wir sehen, dass der DFS-Algorithmus (in zwei Funktionen unterteilt) auf jedem Scheitelpunkt im Diagramm rekursiv aufgerufen wird, um sicherzustellen, dass alle Scheitelpunkte besucht werden.

Laufzeitanalyse

Die zeitliche Komplexität von DFS ist dieselbe wie bei BFS, d.h. O (| V | + | E |) Dabei ist V die Anzahl der Eckpunkte und E die Anzahl der Kanten in einem gegebenen Graphen.

Ähnlich wie bei BFS sind abhängig von der Frage, ob der Graph kaum oder dicht besiedelt ist, der dominierende Faktor Eckpunkte bzw. Kanten bei der Berechnung der Zeitkomplexität.

Iterative DFS

Die oben für die DFS-Technik gezeigte Implementierung ist rekursiver Natur und verwendet einen Funktionsaufrufstapel. Wir haben eine andere Variante für die Implementierung von DFS, d. H. Iterative Tiefensuche ”. In diesem Fall verwenden wir den expliziten Stapel, um die besuchten Scheitelpunkte zu halten.

Wir haben die Implementierung für iterative DFS unten gezeigt. Beachten Sie, dass die Implementierung mit BFS identisch ist, außer dass wir die Stapeldatenstruktur anstelle einer Warteschlange verwenden.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Ausgabe:

Ausgabe der iterativen Tiefendurchquerung:

0 3 2 4 1

Wir verwenden dasselbe Diagramm, das wir in unserer rekursiven Implementierung verwendet haben. Der Unterschied in der Ausgabe besteht darin, dass wir den Stapel in der iterativen Implementierung verwenden. Da die Stapel der LIFO-Reihenfolge folgen, erhalten wir eine andere Sequenz von DFS. Um die gleiche Reihenfolge zu erhalten, möchten wir möglicherweise die Scheitelpunkte in umgekehrter Reihenfolge einfügen.

BFS gegen DFS

Bisher haben wir beide Durchquerungstechniken für Graphen diskutiert, d. H. BFS und DFS.

Lassen Sie uns nun die Unterschiede zwischen den beiden untersuchen.

BFSDFS
Steht für 'Breitensuche'Steht für 'Tiefensuche'
Die Knoten werden Ebene für Ebene in der Breite untersucht.Die Knoten werden in der Tiefe untersucht, bis nur noch Blattknoten vorhanden sind, und dann zurückverfolgt, um andere nicht besuchte Knoten zu untersuchen.
BFS wird mit Hilfe der Warteschlangendatenstruktur durchgeführt.DFS wird mit Hilfe der Stack-Datenstruktur durchgeführt.
Langsamere Leistung.Schneller als BFS.
Nützlich, um den kürzesten Weg zwischen zwei Knoten zu finden.Wird hauptsächlich zum Erkennen von Zyklen in Diagrammen verwendet.

Anwendungen der DFS

  • Zyklen in der Grafik erkennen: Wenn wir beim Ausführen von DFS in einem Diagramm eine Hinterkante finden, können wir daraus schließen, dass das Diagramm einen Zyklus hat. Daher wird DFS verwendet, um die Zyklen in einem Diagramm zu erfassen.
  • Wegfindung: Bei zwei Eckpunkten x und y können wir den Pfad zwischen x und y mithilfe von DFS finden. Wir beginnen mit dem Scheitelpunkt x und schieben dann alle Scheitelpunkte auf dem Weg zum Stapel, bis wir auf y stoßen. Der Inhalt des Stapels gibt den Pfad zwischen x und y an.
  • Minimaler Spannbaum und kürzester Weg: Die DFS-Durchquerung des ungewichteten Graphen ergibt einen minimalen Spannbaum und einen kürzesten Pfad zwischen Knoten.
  • Topologische Sortierung: Wir verwenden die topologische Sortierung, wenn wir die Jobs anhand der angegebenen Abhängigkeiten zwischen Jobs planen müssen. In der Informatik verwenden wir es hauptsächlich zum Auflösen von Symbolabhängigkeiten in Linkern, zur Datenserialisierung, zur Befehlsplanung usw. DFS wird häufig in der topologischen Sortierung verwendet.

Fazit

In den letzten Tutorials haben wir uns eingehender mit den beiden Durchquerungstechniken für Diagramme befasst, d. H. BFS und DFS. Wir haben die Unterschiede sowie die Anwendungen beider Techniken gesehen. BFS und DFS erzielen grundsätzlich das gleiche Ergebnis beim Besuch aller Knoten eines Diagramms, unterscheiden sich jedoch in der Reihenfolge der Ausgabe und in der Art und Weise, wie dies erfolgt.

Wir haben auch die Implementierung beider Techniken gesehen. Während BFS eine Warteschlange verwendet, verwendet DFS Stapel, um die Technik zu implementieren. Damit schließen wir das Tutorial zu Traversal-Techniken für Graphen ab. Wir können BFS und DFS auch für Bäume verwenden.

Wie schreibe ich CSS-Selektor in Selen

In unserem nächsten Tutorial erfahren Sie mehr über das Überspannen von Bäumen und einige Algorithmen, um den kürzesten Weg zwischen den Knoten eines Diagramms zu finden.

=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.

Literatur-Empfehlungen

^