Appearance
深度优先搜索（DFS）
为什么需要深度优先搜索
图是一种复杂的非线性结构，结点之间的关系是多对多的。要处理图中的数据，首先要解决的问题就是：如何系统地访问图中的每一个顶点，且不遗漏、不重复？
深度优先搜索（Depth-First Search, DFS）是图的两种基本遍历策略之一。它模拟"一条路走到黑，走不通再回头"的思路，是递归与回溯思想在图论中的直接体现。408 考研中，DFS 是图遍历章节的核心考点，也是理解连通性判断、拓扑排序等高级算法的基础。
核心思想
DFS 的核心策略：尽可能深地搜索图的分支，走到死胡同时再回溯。
- 递归/栈：DFS 天然适合用递归实现，系统调用栈自动完成回溯；也可以用显式栈模拟
- visited 数组：用
visited[i]标记顶点 i 是否已被访问，防止重复访问（图中可能有环） - 回溯：当前顶点的所有邻接点都已被访问时，沿原路退回到上一个顶点，继续探索其他分支
DFS 的执行过程类似于树的先序遍历：
访问 v → 找到 v 的一个未访问邻接点 w → 访问 w → 继续深入 ...
→ 所有邻接点都已访问 → 回溯到上一层交互可视化
通过下方的交互动画，你可以逐步观察深度优先搜索的执行过程：
操作详解
算法思路
关键步骤：
- 初始化
visited[]数组，所有顶点标记为未访问 - 从起始顶点 v 出发，标记 v 为已访问，执行访问操作
- 依次检查 v 的所有邻接点 w：
- 若 w 未被访问，则递归地对 w 执行 DFS
- 若 w 已被访问，则跳过
- 当 v 的所有邻接点都已被访问，回溯到调用 DFS(v) 的上一个顶点
- 若图为非连通图，需要对每个连通分量分别调用 DFS（遍历
visited[]找未访问的顶点）
邻接矩阵实现
c
#define MAX_VERTEX 100
int visited[MAX_VERTEX];
int G[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
int n; // 顶点数
void DFS(int v) {
visited[v] = 1;
printf("%d ", v); // 访问顶点 v
for (int w = 0; w < n; w++) {
if (G[v][w] == 1 && !visited[w]) {
DFS(w);
}
}
}
// 遍历整个图（处理非连通图）
void DFSTraverse() {
for (int i = 0; i < n; i++)
visited[i] = 0;
for (int i = 0; i < n; i++) {
if (!visited[i])
DFS(i); // 每次调用产生一棵 DFS 生成树
}
}邻接矩阵中查找某个顶点的所有邻接点需要遍历一整行，时间为 O(V)，因此总时间复杂度为 O(V²)。
邻接表实现
c
typedef struct ArcNode {
int adjvex; // 邻接点编号
struct ArcNode *next; // 指向下一条边
} ArcNode;
typedef struct {
int data; // 顶点数据
ArcNode *first; // 指向第一条边
} VNode;
VNode adjList[MAX_VERTEX];
int visited[MAX_VERTEX];
int n;
void DFS(int v) {
visited[v] = 1;
printf("%d ", v);
ArcNode *p = adjList[v].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(p->adjvex);
}
p = p->next;
}
}
void DFSTraverse() {
for (int i = 0; i < n; i++)
visited[i] = 0;
for (int i = 0; i < n; i++) {
if (!visited[i])
DFS(i);
}
}邻接表中每条边只被访问一次（无向图两次），总时间复杂度为 O(V+E)。
DFS 生成树
对连通图进行 DFS，所有经过的边（即递归调用时使用的边）构成一棵DFS 生成树。
- 连通图：一次 DFS 调用产生一棵生成树
- 非连通图：多次 DFS 调用产生一个DFS 生成森林，每个连通分量对应一棵生成树
- 有向图：DFS 生成的是有向生成森林
注意：同一个图的 DFS 生成树不唯一，取决于起始顶点和邻接点的访问顺序。使用邻接矩阵和邻接表得到的 DFS 序列通常不同。
复杂度分析
| 存储方式 | 时间复杂度 | 说明 |
|---|---|---|
| 邻接矩阵 | O(V²) | 每个顶点需扫描一整行找邻接点 |
| 邻接表 | O(V+E) | 每个顶点只访问其邻接边 |
空间复杂度：O(V)。需要 visited[] 数组（O(V)）以及递归调用栈（最坏 O(V)，当图退化为链时）。
| 对比项 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归调用栈） | 队列 |
| 思想 | 尽可能深入，回溯 | 逐层扩展 |
| 时间复杂度（邻接表） | O(V+E) | O(V+E) |
| 时间复杂度（邻接矩阵） | O(V²) | O(V²) |
| 空间复杂度 | O(V) | O(V) |
| 最短路径 | 不能求无权图最短路径 | 可以求无权图最短路径 |
| 适用场景 | 连通性、路径搜索、拓扑排序 | 最短路径、层次遍历 |
考研高频考点
- ⭐ 给定图的邻接矩阵/邻接表，写出 DFS 序列（选择题/填空题高频）
- ⭐ DFS 与 BFS 的对比：数据结构、适用场景、能否求最短路径（简答题必考）
- ⭐ DFS 生成树/生成森林的构造（画图题常考）
- ⭐ 用 DFS 判断图的连通性：无向图连通分量个数 = DFSTraverse 中调用 DFS 的次数
- 邻接矩阵 vs 邻接表下 DFS 时间复杂度的区别及原因
- DFS 非递归实现（用显式栈模拟）
- DFS 的应用：判断有向图是否有环、求连通分量