Depth First Search oder Depth First Traversal ist ein rekursiver Algorithmus zum Durchsuchen aller Eckpunkte eines Diagramms oder einer Baumdatenstruktur. Traversal bedeutet, alle Knoten eines Graphen zu besuchen.
Erster Tiefensuchalgorithmus
Eine Standard-DFS-Implementierung legt jeden Scheitelpunkt des Diagramms in eine von zwei Kategorien:
- Besucht
- Nicht besucht
Der Zweck des Algorithmus besteht darin, jeden Scheitelpunkt als besucht zu markieren, während Zyklen vermieden werden.,
Der DFS-Algorithmus funktioniert wie folgt:
- Setzen Sie zunächst einen beliebigen Scheitelpunkt des Diagramms auf einen Stapel.
- Nehmen Sie das oberste Element des Stapels und fügen Sie es der besuchten Liste hinzu.
- Erstellen Sie eine Liste der benachbarten Knoten dieses Scheitelpunkts. Fügen Sie diejenigen, die nicht in der besuchten Liste enthalten sind, oben im Stapel hinzu.
- Wiederholen Sie die Schritte 2 und 3 so lange, bis der Stapel leer ist.
Tiefensuchbeispiel
Lassen Sie uns sehen, wie der Tiefensuchalgorithmus mit einem Beispiel funktioniert. Wir verwenden einen ungerichteten Graphen mit 5 Eckpunkten.,
Wir beginnen mit Scheitelpunkt 0.
Als nächstes besuchen wir das Element oben im Stapel, dh 1, und gehen zu seinen benachbarten Knoten. Da 0 bereits besucht wurde, besuchen wir stattdessen 2.,
Vertex 2 hat einen nicht besuchten benachbarten Vertex in 4, also fügen wir das oben auf dem Stapel hinzu und besuchen es.
Nachdem wir das letzte Element 3 besucht haben, hat es keine nicht besuchten benachbarten Knoten, so dass wir die Tiefe abgeschlossen haben Erste Durchquerung des Graphen.,
DFS Pseudocode (rekursive Implementierung)
Der pseudocode für die DFS ist unten dargestellt. Beachten Sie in der Funktion init (), dass wir die DFS-Funktion auf jedem Knoten ausführen. Dies liegt daran, dass das Diagramm möglicherweise zwei verschiedene getrennte Teile hat, sodass wir, um sicherzustellen, dass wir jeden Scheitelpunkt abdecken, auch den DFS-Algorithmus auf jedem Knoten ausführen können.,
DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}
DFS-Implementierung in Python, Java und C/C++
Der Code für den Tiefensuchalgorithmus mit einem Beispiel ist unten dargestellt. Der Code wurde vereinfacht, sodass wir uns eher auf den Algorithmus als auf andere Details konzentrieren können.
Komplexität der Tiefensuche
Die zeitliche Komplexität des DFS-Algorithmus wird in Form von O(V + E) dargestellt, wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
Die Raumkomplexität des Algorithmus ist O(V).,
Anwendung des DFS-Algorithmus
- Zum Finden des Pfades
- Zum Testen, ob der Graph zweigliedrig ist
- Zum Finden der stark verbundenen Komponenten eines Graphen
- Zum Erkennen von Zyklen in einem Graphen