本课时有配套视频讲解，购买后即可观看（永久有效）
图的深度优先遍历
一、课上练习
编程练习
二、知识总结
✨ 核心思想
图的深度优先遍历（DFS，Depth-First Search）是一种用于遍历或搜索图中所有顶点的算法。这种方法沿图的边探索尽可能深的路径，直到无法继续，然后回溯到之前的顶点，以探索未访问的路径。深度优先遍历对于解决许多图相关问题非常有效，如路径查找、拓扑排序、检测环等。
在进行深度优先搜索时，每个顶点都被标记为已访问，以避免重复访问和可能的无限循环。DFS 可以应用于有向图和无向图，并且可以从图中的任意顶点开始遍历。
✨ 深度优先遍历的特点
- 深度优先遍历可能不会访问图中的所有顶点，特别是在非连通图中。在这种情况下，可能需要从多个顶点开始遍历，以确保每个组件都被探索。
- DFS 可以揭示图的许多性质，如检测环，找到图中的连通分量等。
- 在有向图中，DFS 的顺序可以帮助进行拓扑排序。
深度优先搜索是图论中的基础算法之一，理解并能够实现它对于深入学习更复杂的图算法至关重要。
✨ 执行示例
下面用一个具体的有向图，完整展示 DFS 的递归执行过程。
示例图： 5 个顶点，6 条边
0 --> 1 --> 3
| |
v v
2 --> 4邻接表：
- 0: [1, 2]
- 1: [3, 4]
- 2: [4]
- 3: []
- 4: []
从顶点 0 开始 DFS：
| 步骤 | 操作 | visited 状态 | 输出 | 递归调用栈 |
|---|---|---|---|---|
| 1 | 访问 0 | [T,F,F,F,F] | 0 | DFS(0) |
| 2 | 0 的邻居 1 未访问，递归 | [T,T,F,F,F] | 0 1 | DFS(0)->DFS(1) |
| 3 | 1 的邻居 3 未访问，递归 | [T,T,F,T,F] | 0 1 3 | DFS(0)->DFS(1)->DFS(3) |
| 4 | 3 没有邻居，返回到 DFS(1) | [T,T,F,T,F] | 0 1 3 | DFS(0)->DFS(1) |
| 5 | 1 的邻居 4 未访问，递归 | [T,T,F,T,T] | 0 1 3 4 | DFS(0)->DFS(1)->DFS(4) |
| 6 | 4 没有邻居，返回到 DFS(1) | [T,T,F,T,T] | 0 1 3 4 | DFS(0)->DFS(1) |
| 7 | 1 的邻居都已访问，返回到 DFS(0) | [T,T,F,T,T] | 0 1 3 4 | DFS(0) |
| 8 | 0 的邻居 2 未访问，递归 | [T,T,T,T,T] | 0 1 3 4 2 | DFS(0)->DFS(2) |
| 9 | 2 的邻居 4 已访问，跳过 | [T,T,T,T,T] | 0 1 3 4 2 | DFS(0)->DFS(2) |
| 10 | 返回到 DFS(0)，所有邻居处理完毕 | [T,T,T,T,T] | 0 1 3 4 2 | 空 |
DFS 遍历结果：0 1 3 4 2
注意 DFS 的特点：它会沿着一条路径尽可能深入（0->1->3），然后回溯再探索其他分支（1->4），最后才回到 0 探索另一条路径（0->2）。
✨ 解题步骤详解
以"最长路径"为例，展示如何用 DFS 解决图上的问题：
问题： 在有向无环图（DAG）中，求从任意顶点出发的最长路径长度。
解题步骤：
- 建图：用邻接表存储有向图。
- 对每个顶点执行 DFS：从该顶点出发，递归计算能走的最远距离。
- DFS 函数设计：
1int dfs(int v):
2 if v 已计算过最长路径: 返回缓存值
3 maxLen = 0
4 for 每个邻居 u of v:
5 maxLen = max(maxLen, 1 + dfs(u))
6 缓存 v 的最长路径 = maxLen
7 return maxLen- 记忆化：用数组记录每个顶点的最长路径，避免重复计算（同一个顶点可能从不同路径到达）。
- 取所有顶点中的最大值作为答案。
关键点： DFS + 记忆化可以将时间复杂度从指数级降低到 O(V+E)。
✨ 常见错误
- 忘记标记 visited：不标记已访问节点会导致在有环图中无限递归，在无环图中也会重复访问导致超时。
- visited 数组没有回溯：在某些问题中（如求所有路径），DFS 结束后需要将 visited 标记恢复为 false，以允许其他路径经过该节点。在求连通性时则不需要回溯。
- 邻接表的遍历顺序影响结果：DFS 的遍历结果取决于邻居的访问顺序。不同的邻接表存储顺序会导致不同的 DFS 序列（但都是合法的 DFS 结果）。
- 递归深度过大导致栈溢出：当图有上万个顶点时，递归 DFS 可能导致栈溢出。此时应使用非递归实现（手动维护栈）。
- 混淆 DFS 和回溯：DFS 是图遍历的一种方式，回溯是在搜索空间中探索并撤销选择的算法范式。回溯通常基于 DFS 实现，但两者的目的不同。
✨ 实现方法
深度优先遍历可以通过递归实现，也可以通过显式使用栈来实现。
递归实现
递归实现是最直观的方法，每个顶点在被访问时标记为已访问，并递归地访问其所有未访问的邻接顶点。
DFS递归实现代码示例
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Graph {
6 int V; // 顶点数
7 vector<int> *adj; // 邻接表
8public:
9 Graph(int V); // 构造函数
10 void addEdge(int v, int w); // 添加边
11 void DFS(int v, vector<bool> &visited); // DFS从顶点v开始
12};
13
14Graph::Graph(int V) {
15 this->V = V;
16 adj = new vector<int>[V];
17}
18
19void Graph::addEdge(int v, int w) {
20 adj[v].push_back(w); // 添加v到w的边
21}
22
23void Graph::DFS(int v, vector<bool> &visited) {
24 visited[v] = true; // 标记当前节点为已访问
25 cout << v << " ";
26 // 递归遍历所有未访问的邻接顶点
27 for (int i = 0; i < adj[v].size(); i++) {
28 int next = adj[v][i];
29 if (!visited[next])
30 DFS(next, visited);
31 }
32}
33
34int main() {
35 Graph g(4); // 创建一个图，顶点编号从0到3
36 g.addEdge(0, 1);
37 g.addEdge(0, 2);
38 g.addEdge(1, 2);
39 g.addEdge(2, 0);
40 g.addEdge(2, 3);
41 g.addEdge(3, 3);
42
43 vector<bool> visited(4, false);
44 g.DFS(2, visited); // 从顶点2开始DFS遍历
45 return 0;
46}非递归实现（栈）
非递归实现使用一个栈来模拟递归过程：
DFS非递归实现代码示例
1void Graph::DFS_iterative(int v) {
2 vector<bool> visited(V, false);
3 stack<int> stk;
4 stk.push(v); // 将起始顶点放入栈
5 while (!stk.empty()) {
6 v = stk.top();
7 stk.pop();
8 if (!visited[v]) {
9 visited[v] = true;
10 cout << v << " ";
11 }
12 // 将所有未访问的邻接顶点放入栈
13 for (auto i = adj[v].rbegin(); i != adj[v].rend(); ++i) {
14 if (!visited[*i])
15 stk.push(*i);
16 }
17 }
18}三、课后练习
编程练习
- 马走日: L3343