In diesem Tutorial lernen Sie den Tiefensuchalgorithmus mit Beispielen und Pseudocode kennen. Außerdem lernen Sie, DFS in C, Java, Python und C ++ zu implementieren.
Tiefe zuerst suchen oder Tiefe zuerst durchlaufen ist ein rekursiver Algorithmus zum Durchsuchen aller Eckpunkte eines Graphen oder einer Baumdatenstruktur. Durchqueren bedeutet, alle Knoten eines Graphen zu besuchen.
Tiefensuchalgorithmus
Bei einer Standard-DFS-Implementierung wird jeder Scheitelpunkt des Diagramms in eine von zwei Kategorien eingeteilt:
- hat besucht
- Nicht besucht
Der Zweck des Algorithmus besteht darin, jeden Scheitelpunkt als besucht zu markieren und dabei Zyklen zu vermeiden.
Der DFS-Algorithmus funktioniert wie folgt:
- Legen Sie zunächst einen der Scheitelpunkte 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.
Beispiel für die Tiefe der ersten Suche
Lassen Sie uns anhand eines Beispiels sehen, wie der Algorithmus für die Tiefensuche funktioniert. Wir verwenden einen ungerichteten Graphen mit 5 Eckpunkten.
Ungerichteter Graph mit 5 Eckpunkten
Wir beginnen mit Scheitelpunkt 0, der DFS-Algorithmus beginnt damit, ihn in die Liste "Besucht" aufzunehmen und alle benachbarten Scheitelpunkte in den Stapel zu legen.
Besuchen Sie das Element und fügen Sie es in die besuchte Liste ein
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.
Besuchen Sie das Element oben im Stapel
Vertex 2 hat einen nicht besuchten benachbarten Vertex in 4, also fügen wir diesen oben im Stapel hinzu und besuchen ihn.
Vertex 2 hat einen nicht besuchten benachbarten Vertex in 4, also fügen wir diesen oben im Stapel hinzu und besuchen ihn. 
Vertex 2 hat einen nicht besuchten benachbarten Vertex in 4, also fügen wir diesen oben im Stapel hinzu und besuchen ihn.
Nachdem wir das letzte Element 3 besucht haben, hat es keine nicht besuchten benachbarten Knoten, daher haben wir die erste Tiefenüberquerung des Graphen abgeschlossen.
Nachdem wir das letzte Element 3 besucht haben, hat es keine nicht besuchten benachbarten Knoten, daher haben wir die erste Tiefenüberquerung des Graphen abgeschlossen.
DFS-Pseudocode (rekursive Implementierung)
Der Pseudocode für 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 enthält. Um sicherzustellen, dass wir jeden Scheitelpunkt abdecken, können wir den DFS-Algorithmus auch auf jedem Knoten ausführen.
DFS (G, u) u.visited = true für jedes v ∈ G.Adj (u) wenn v.visited == false DFS (G, v) init () (für jedes u ∈ G u.visited = false für jedes u ∈ G DFS (G, u))
DFS-Implementierung in Python, Java und C / C ++
Der Code für den Algorithmus für die Tiefensuche mit einem Beispiel ist unten dargestellt. Der Code wurde vereinfacht, damit wir uns eher auf den Algorithmus als auf andere Details konzentrieren können.
Python Java C C + # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')
// DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )
// DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )
// DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )
Komplexität der Tiefensuche
Die zeitliche Komplexität des DFS-Algorithmus wird in Form von dargestellt O(V + E), wobei Vdie Anzahl der Knoten und Edie Anzahl der Kanten ist.
Die räumliche Komplexität des Algorithmus ist O(V).
Anwendung des DFS-Algorithmus
- Um den Weg zu finden
- Um zu testen, ob der Graph zweiteilig ist
- Zum Finden der stark verbundenen Komponenten eines Graphen
- Zum Erkennen von Zyklen in einem Diagramm
