深度优先搜索（DFS）
最后更新
深度优先搜索在探索图时，会沿着每条分支尽可能深入，然后再回溯。它从源节点出发，访问一个邻居，再访问这个邻居的邻居，依此类推，直到走进死胡同（一个没有未访问邻居的节点），这时它回溯并尝试下一条分支。点击上方的“播放”，观察它如何沿一条路径深入到底，再退回来。
DFS 天然适合用栈来表达：可以是显式的栈（如这里的动画），也可以是递归时的调用栈。它对每个节点和每条边各访问一次，所以对一个有 V 个顶点、E 条边的图，运行时间是 O(V + E)。
时间和空间复杂度
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(V + E) | 每个顶点和每条边各访问一次 |
| 空间 | O(V) | 栈加已访问集合，最坏情况包含所有节点 |
| 遍历方式 | 深度优先 | 先把一条分支走到底，再走其他分支 |
| 数据结构 | 栈（或递归） | 后进先出的顺序决定了深度优先的行为 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 把源节点压入栈。 |
| 2 | 弹出一个节点；如果它已被访问，就跳过。 |
| 3 | 把它标记为已访问，并记录到达它的那条边。 |
| 4 | 把它所有未访问的邻居压入栈。 |
| 5 | 重复，直到栈为空。 |
示例演算
在图 A → [B, C]、B → [D]、C → [E] 上从 A 开始迭代式 DFS，邻居按列出的顺序入栈（后进先出的栈会先弹出最后压入的元素）：
| 步骤 | 栈（右侧为栈顶） | 已访问 | 操作 |
|---|---|---|---|
| 1 | [A] | {} | 压入源节点 A。 |
| 2 | [B, C] | {A} | 弹出 A，标记为已访问，依次压入邻居 B 和 C。 |
| 3 | [B, E] | {A, C} | 弹出 C，标记为已访问，压入邻居 E。 |
| 4 | [B] | {A, C, E} | 弹出 E，标记为已访问，它没有邻居。 |
| 5 | [D] | {A, C, E, B} | 弹出 B，标记为已访问，压入邻居 D。 |
| 6 | [] | {A, C, E, B, D} | 弹出 D，标记为已访问，栈已空，结束。 |
什么时候使用 DFS
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
| 需要做环检测、拓扑排序，或者找连通分量。 | 需要在无权图中找最短路径，BFS 能做到，DFS 不能。 |
| 图又宽又浅，栈占用的内存远少于存放大量待访问节点的队列。 | 图非常深并且用了递归，调用栈可能会溢出。 |
| 想穷举所有路径，比如走迷宫或回溯搜索。 | 需要按离源节点的距离顺序发现节点。 |
| 要检查可达性，或者判断两个节点之间是否存在路径。 | 必须保证找到的路径边数最少。 |
Depth-First Search 代码
简洁、可运行的 Depth-First Search 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Depth-First Search 的 Python 代码
Python
1def dfs(graph, node, visited):2 visited.add(node)3 order = [node]4 for neighbor in graph[node]:5 if neighbor not in visited:6 order.extend(dfs(graph, neighbor, visited))7 return order8
9
10graph = {11 "A": ["B", "C"],12 "B": ["D", "E"],13 "C": ["F"],14 "D": [],15 "E": ["F"],16 "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))Depth-First Search 的 JavaScript 代码
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11 if (visited.has(node)) return order;12 visited.add(node);13 order.push(node);14 for (const next of graph[node]) {15 dfs(next, visited, order);16 }17 return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));Depth-First Search 的 Java 代码
Java
1import java.util.List;2
3public class Main {4 static List<List<Integer>> adj = List.of(5 List.of(1, 2), // neighbors of 06 List.of(0, 3, 4), // neighbors of 17 List.of(0, 5), // neighbors of 28 List.of(1),9 List.of(1, 5),10 List.of(2, 4)11 );12 static boolean[] visited = new boolean[6];13
14 static void dfs(int node) {15 visited[node] = true;16 System.out.print(" " + node);17 for (int next : adj.get(node)) {18 if (!visited[next]) dfs(next);19 }20 }21
22 public static void main(String[] args) {23 System.out.print("DFS from 0:");24 dfs(0);25 System.out.println();26 }27}Depth-First Search 的 C++ 代码
C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5 std::vector<bool>& visited) {6 visited[node] = true;7 std::cout << node << " ";8 // Recurse into every unvisited neighbor9 for (int next : adj[node]) {10 if (!visited[next]) dfs(next, adj, visited);11 }12}13
14int main() {15 // 6-node undirected graph as an adjacency list16 std::vector<std::vector<int>> adj = {17 {1, 2}, // 018 {0, 3, 4}, // 119 {0, 5}, // 220 {1}, // 321 {1, 5}, // 422 {2, 4}, // 523 };24 std::vector<bool> visited(adj.size(), false);25 std::cout << "DFS from node 0: ";26 dfs(0, adj, visited);27 std::cout << "\n";28 return 0;29}Depth-First Search 的 C 代码
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8 {0, 1, 1, 0, 0, 0},9 {1, 0, 0, 1, 1, 0},10 {1, 0, 0, 0, 0, 1},11 {0, 1, 0, 0, 0, 0},12 {0, 1, 0, 0, 0, 1},13 {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18 visited[node] = true;19 printf("%d ", node);20 // Recurse into every unvisited neighbor21 for (int next = 0; next < N; next++) {22 if (adj[node][next] && !visited[next]) dfs(next);23 }24}25
26int main(void) {27 printf("DFS from node 0: ");28 dfs(0);29 printf("\n");30 return 0;31}深度优先搜索常见问题
DFS 的时间复杂度是多少？
DFS 的运行时间是
O(V + E)，其中 V 是顶点数，E 是边数，因为它对每个顶点访问一次，对每条边查看一次。栈和已访问集合占用 O(V) 的空间。DFS 和 BFS 有什么区别？
DFS 是递归的还是迭代的？
两种都可以。递归版本隐式地使用程序的调用栈，写起来非常简洁；迭代版本使用显式的栈（如这里的动画），在大图上可以避免深层递归导致的栈溢出。
什么时候该用 DFS 而不是 BFS？
当你需要探索完整的路径时用 DFS：环检测、拓扑排序、连通分量，或者走迷宫这类回溯搜索。它在宽图上占用的内存也更少，因为栈一次只保存一条分支上的待访问节点。如果需要无权图中的最短路径，或者需要按离源节点的距离顺序得到节点，就改用 BFS。
DFS 能找到最短路径吗？
不可靠。DFS 返回它碰巧找到的第一条路径，而这往往不是边数最少的那条，因为它一心向深处走，而不是均匀地向外扩展。无权图的最短路径请用 BFS，带权图请用 Dijkstra 算法。
为什么 DFS 需要已访问集合？
没有已访问集合，DFS 会重复访问可以通过多条路径到达的节点，在有环的图中还会陷入无限循环。在弹出节点时标记已访问（并跳过已访问的节点），能保证每个节点只处理一次，运行时间保持在
O(V + E)。一个常见的错误是只在弹出时标记已访问，却仍然压入重复节点：这样结果是对的，但栈里会留下过时的条目，必须跳过。相关资源
更多可视化
