# DFS 算法 > 原文： [https://www.programiz.com/dsa/graph-dfs](https://www.programiz.com/dsa/graph-dfs) #### 在本教程中，您將學習什么是 DFS 算法。 此外，您還將找到 C，C++ ，Java 和 Python 中 DFS 算法的工作示例。 遍歷意味著訪問[圖](/dsa/graph)的所有節點。 深度優先遍歷或深度優先搜索是一種用于搜索圖形或樹數據結構的所有頂點的遞歸算法。 在本文中，您將通過示例學習 DFS 算法，DFS 偽代碼以及深度優先搜索算法的代碼，并在 C++ ，C，Java 和 Python 程序中實現。 * * * ## DFS 算法 一個標準的 DFS 實現將圖形的每個頂點分為以下兩類之一： 1. 已訪問 2. 未訪問 該算法的目的是將每個頂點標記為已訪問，同時避免循環。 DFS 算法的工作原理如下： 1. 首先將圖形的任意一個頂點放在棧的頂部。 2. 取得棧的頂部項目并將其添加到已訪問列表。 3. 創建該頂點的相鄰節點的列表。 將不在訪問列表中的那些添加到棧的頂部。 4. 繼續重復步驟 2 和 3，直到棧為空。 * * * ## DFS 示例 讓我們來看一個深度優先搜索算法的示例。 我們使用具有 5 個頂點的無向圖。  具有 5 個頂點的無向圖 我們從頂點 0 開始，DFS 算法首先將其放置在`Visited`列表中，然后將其所有相鄰的頂點放置在棧中。  訪問元素并將其放在訪問列表中 接下來，我們訪問棧頂部即 1 的元素并轉到其相鄰節點。 由于已經訪問過 0，因此我們訪問 2。  訪問棧頂部的元素 頂點 2 在 4 中有一個未訪問的相鄰頂點，因此我們將其添加到棧的頂部并對其進行訪問。  頂點 2 在 4 中有一個未訪問的相鄰頂點，因此我們將其添加到棧的頂部并對其進行訪問。  頂點 2 在 4 中有一個未訪問的相鄰頂點，因此我們將其添加到棧的頂部并對其進行訪問。 在訪問最后一個元素 3 之后，它沒有任何未訪問的相鄰節點，因此我們完成了圖的“深度優先遍歷”。  在訪問最后一個元素 3 之后，它沒有任何未訪問的相鄰節點，因此我們完成了圖的深度優先遍歷。 * * * ## DFS 偽代碼（遞歸實現） DFS 的偽代碼如下所示。 在`init()`函數中，請注意，我們在每個節點上都運行 DFS 函數。 這是因為圖形可能具有兩個不同的斷開部分，因此為了確保覆蓋每個頂點，我們還可以在每個節點上運行 DFS 算法。 ``` DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u) } ``` * * * ## Python，Java 和 C/C++ 示例 下面顯示了深度優先搜索算法的代碼和示例。 代碼已經簡化，因此我們可以專注于算法而不是其他細節。 ```py # 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') ``` ```java // DFS algorithm in Java import java.util.*; class Graph { private LinkedList<Integer> 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<Integer>(); } // 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<Integer> 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); } } ``` ```c // DFS algorithm in C #include <stdio.h> #include <stdlib.h> 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 \n", 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 < vertices; i++) { graph->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 < graph->numVertices; v++) { struct node* temp = graph->adjLists[v]; printf("\n Adjacency list of vertex %d\n ", v); while (temp) { printf("%d -> ", temp->vertex); temp = temp->next; } printf("\n"); } } 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; } ``` ```cpp // DFS algorithm in C++ #include <iostream> #include <list> using namespace std; class Graph { int numVertices; list<int> *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<int>[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<int> adjList = adjLists[vertex]; cout << vertex << " "; list<int>::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; } ``` * * * ## DFS 算法復雜度 DFS 算法的時間復雜度以`O(V + E)`的形式表示，其中`V`是節點數，`E`是邊數。 該算法的空間復雜度為`O(V)`。 * * * ## DFS 算法應用 1. 尋找路徑 2. 測試圖是否為二分圖 3. 用于查找圖的強連接組件 4. 用于檢測圖中的循環