深度优先搜索（DFS）

2026 大纲 五（三）图的遍历 1. 深度优先搜索（第 2 小项见《BFS》）。

一条路走到黑，走不动了才退回岔口

DFS 的策略只有一句话：尽可能沿一条路径深入，走到无路可走时才退回上一个岔口换方向。它就是二叉树先序遍历在图上的推广——先序遍历也是"访问根，然后一头扎进左子树，左边走完才轮到右边"。

既然是先序遍历的推广，为什么代码不能照抄？因为树和图之间有一处根本差别：图里有环。

树里从根到任一结点的路径唯一，一个结点不可能被访问两次。图里不然，沿环走一圈就会回到已经访问过的顶点。所以图的遍历必须多带一个数组：

🔴 visited[] 是图遍历的强制配件，没有它，DFS 在有环图上会无限递归。

而且置位的时机也是硬性的：

void DFS(int v) {
    visited[v] = 1;               // ← 必须在这里，不能挪到 for 之后
    printf("%d ", v);
    for (int w = 0; w < n; w++)
        if (G[v][w] == 1 && !visited[w])
            DFS(w);
}

若把置位挪到 for 循环之后（"等孩子都处理完再置位"），有环图上从 $v$ 出发绕环回到 $v$ 时，visited[v] 还是 0，于是再次进入 DFS(v)，直到栈溢出。"先置位后展开"是所有图遍历的通用纪律，BFS 那边同样如此（入队时置位，不是出队时）。

先动手看一眼

加载可视化中...

拨的时候盯两处：一是回溯——看清"退回上一个岔口"发生在什么时刻；二是换一个起点重跑，看序列怎么整个变掉。后面判"某序列是不是合法 DFS 序"的题，靠的就是对这两件事的手感。

两种存储结构下的实现

// ── 邻接表版：只走自己的链
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;              // 🔴 必须在 if 之外：写进分支里，遇到已访问的邻居
    }                             //    指针不推进，while 原地死循环
}

// ── 遍历整个图（处理非连通图）
void DFSTraverse(void) {
    for (int i = 0; i < n; i++) visited[i] = 0;
    for (int i = 0; i < n; i++)
        if (!visited[i]) DFS(i);  // 每次调用产生一棵 DFS 生成树
}

外层那个循环不能省。 一次 DFS(v) 只能走遍 $v$ 所在的一个连通分量，非连通图会漏掉其余部分。由此还得到一条常用结论：外层启动 DFS 的次数 = 无向图连通分量的个数（⚠️ 对有向图不成立，反例见下面的折叠块）。

复杂度分两种存储：

邻接矩阵 $O (n^{2})$ ：DFS 总共被调用 $n$ 次，每次内层 for 固定跑 $n$ 趟——即使这个顶点只有 1 个邻居，也得扫完一整行才知道其余都不是。与边数完全无关。
邻接表 $O (n + e)$ ： $n$ 次调用的固定开销给出 $n$ ，每个边结点恰好被检查一次给出 $e$ （有向图 $e$ 个边结点、无向图 $2 e$ 个）。⚠️ 和号里的 $n$ 不能省， $e = 0$ 时仍要 $O (n)$ 。

空间都是 $O (n)$ ：visited[] 占 $O (n)$ ，递归栈的深度等于 DFS 树的最大深度——链形图最坏能到 $n$ ，星形图只有 2。写 $O (n)$ 说的是最坏情形。

DFS 序列不唯一，以及怎么数有几个

这是选择题最爱下手的地方，得说透。

序列由两件事决定：从哪个顶点出发，以及每个顶点的邻接点按什么次序被检查。后者取决于存储结构：

用邻接表存，链上次序由建表方式决定，所以序列不唯一。
用邻接矩阵存，内层固定按下标升序扫行，起点一旦确定，序列就唯一。

考试默认前提是"邻接表次序未定"，所以合法的 DFS 序列通常有好几个。于是有两类问法。

第一类：数一数有多少个不同的 DFS 序列。 这里有个坑——不能拿"起点的邻居有几个"直接算排列数。

看一个具体的图： $V = {v_{0}, v_{1}, v_{2}, v_{3}}$ ， $E = {⟨ v_{0}, v_{1} ⟩, ⟨ v_{0}, v_{2} ⟩, ⟨ v_{0}, v_{3} ⟩, ⟨ v_{1}, v_{3} ⟩}$ ，从 $v_{0}$ 出发。

$v_{0}$ 有 3 个出邻居，直觉上是 $3! = 6$ 种。但真实答案是 5，因为先选 $v_{1}$ 时， $v_{3}$ 会被顺带拖走：

$v_{0}$ 先进谁	展开过程	得到的序列
$v_{1}$	$v_{1}$ 只有出边到 $v_{3}$ ，必然接着进 $v_{3}$ ；回到 $v_{0}$ 只剩 $v_{2}$	$v_{0} v_{1} v_{3} v_{2}$ （只此 1 种）
$v_{2}$	$v_{2}$ 无出边，立即回溯；再选 $v_{1}$ 或 $v_{3}$	$v_{0} v_{2} v_{1} v_{3}$ ／ $v_{0} v_{2} v_{3} v_{1}$
$v_{3}$	$v_{3}$ 无出边，立即回溯；再选 $v_{1}$ 或 $v_{2}$	$v_{0} v_{3} v_{1} v_{2}$ ／ $v_{0} v_{3} v_{2} v_{1}$

合计 $1 + 2 + 2 = 5$ 。先进 $v_{1}$ 那一支只贡献 1 种，因为深入过程中 $v_{3}$ 已经被访问，回到 $v_{0}$ 时它不再是一个可选分支了。 这就是排列数算法失效的原因：分支之间不独立。

所以数这类题的方法是按第一个分支分类，逐支往下展开，别套公式。

第二类：判某个序列是不是合法的 DFS 序。 逐个顶点核对"它是不是前一个顶点的未访问邻居；如果不是，那么前面某个顶点回溯之后能不能轮到它"。⚠️ 千万别按"编号从小到大"这一种固定次序去模拟——那样会把好几个合法选项判成非法。

生成树、非树边与判环

把所有"引起某个顶点首次被访问"的边挑出来，加上全部顶点，就是 DFS 生成树；非连通图每个分量各一棵，合称生成森林。它的形状明显细长（BFS 树则是扁宽的）。

剩下那些没被选中的边叫非树边，它们携带着判环的信息：

🔴 无向图上每条非树边都连接着树上的一对祖先—后代，必然与树边围成一个环。所以无向图有环 $⟺$ 出现非树边 $⟺$ 边数 $> n - k$ （ $k$ 为连通分量个数）。

有向图的判环要更细一点，因为"指向已访问顶点"不一定成环——那个顶点可能早就处理完、已经不在当前这条路径上了。区分办法是三色标记，代码在下面的折叠块里。

顺带一句："两张图的 DFS 序列相同"推不出"两张图相同"。序列只记录了顶点的访问次序，把非树边的信息全丢了。

一处改动，DFS 变成逆拓扑排序

这是 DFS 上最值得单独记的一个变形，而且真题直接考过。

标准 DFS 在进入递归时输出顶点。现在把输出语句挪到退出递归之前：

void DFS2(int v) {
    visited[v] = 1;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        if (!visited[w]) DFS2(w);
    printf("%d ", v);             // ← 挪到这里：所有后代都处理完了，才轮到自己
}

在有向无环图上跑这个改法，若输出包含了全部顶点，得到的是逆拓扑有序序列——把它整个反过来，才是拓扑序列。

为什么？一个顶点被输出，说明它的所有后继都已经输出完毕。也就是说，每个顶点都排在它的所有后继之后——这正是"拓扑序列反过来"的定义。

⚠️ 别把结论记成"拓扑序列"。挪了输出位置得到的是逆拓扑序，方向反了整道题就错。选项里通常同时摆着"拓扑有序序列"和"逆拓扑有序序列"两个，就是冲这个来的。

七顶点无向图的 DFS 序列走查，以及换一份邻接表序列就变（想手动模拟就展开）

$E = {(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (4, 5)}$ ，邻接表按编号升序建立：

顶点	边链表
0	1 → 2
1	0 → 3 → 4
2	0 → 5 → 6
3	1
4	1 → 5
5	2 → 4
6	2

从顶点 0 出发的执行过程：

步	当前顶点	检查到的邻居	动作	已输出序列
1	0	1（未访问）	访问 0，递归进 1	0
2	1	0（已访问）→ 3	访问 1，跳过 0，递归进 3	0 1
3	3	1（已访问）	访问 3，链走完，回溯到 1	0 1 3
4	1	4（未访问）	递归进 4	0 1 3
5	4	1（已访问）→ 5	访问 4，递归进 5	0 1 3 4
6	5	2（未访问）	访问 5，递归进 2	0 1 3 4 5
7	2	0（已访问）→ 5（已访问）→ 6	访问 2，递归进 6	0 1 3 4 5 2
8	6	2（已访问）	访问 6，链走完，逐层回溯至 0	0 1 3 4 5 2 6

DFS 序列：0 1 3 4 5 2 6。

换一份邻接表，序列就变了：把顶点 0 的链改成 2 → 1（其余不变），第一步就先进 2，得到 0 2 5 4 1 3 6。

这张图的 DFS 生成树：7 条原图边中被用来"首次到达"某顶点的有 6 条—— $(0, 1), (1, 3), (1, 4), (4, 5), (5, 2), (2, 6)$ ，恰好 $n - 1 = 6$ 条。剩下的 $(0, 2)$ 是非树边：轮到顶点 0 检查邻居 2 时（它在链上排第二），2 已被 5 提前访问过了。

无向图的深度优先搜索过程与它的 DFS 树

图注：左图中每个顶点旁的数字是它被访问的次序（ $A$ 第 1 个、 $B$ 第 2 个……）， 实线箭头是"深入"，虚线箭头是"回溯"——注意每条虚线都严格沿着来时的实线原路返回，这正是递归调用栈弹栈的样子。右图把左图中所有实线箭头对应的边单独抽出来，就是 DFS 树。图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.12 深度优先搜索示例，p364

非递归实现：显式栈版本（被问到"DFS 的非递归写法"时展开）

void DFS_NonRecursive(int v) {
    int stack[MAX_VERTEX], top = -1;
    stack[++top] = v;
    while (top >= 0) {
        int u = stack[top--];             // 出栈
        if (visited[u]) continue;         // 同一顶点可能被多次入栈，出栈时再判一次
        visited[u] = 1;
        printf("%d ", u);
        for (int w = n - 1; w >= 0; w--)  // 逆序入栈，使出栈次序与递归版一致
            if (G[u][w] == 1 && !visited[w])
                stack[++top] = w;
    }
}

两处与递归版不同、且必须理解的地方：

出栈时还要再判一次 visited。一个顶点可能在被弹出之前，从多条不同的边被重复压栈；只在入栈时判、出栈时不判，同一个顶点会被访问多次。
入栈顺序要逆序，才能让出栈顺序与递归版的"按邻接次序依次深入"一致。若按正序入栈，得到的是另一个合法 DFS 序列——它同样合法，只是与递归版不同，这本身就说明了 DFS 序列不唯一。

用 DFS 数无向图连通分量，以及为什么这招在有向图上完全失效

int countComponents(void) {
    for (int i = 0; i < n; i++) visited[i] = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (!visited[i]) { DFS(i); cnt++; }   // 每启动一次 DFS 就多一个分量
    return cnt;
}

正确性：一次 DFS(i) 恰好访问 $i$ 所在连通分量的全部顶点且不会越出该分量（越出就意味着有跨分量的边，与"分量"的定义矛盾）。

走查：7 个顶点，边为 $(0, 1), (1, 2), (3, 4), (5, 6)$ ，邻接表升序。

外层 $i$	`visited[i]`	动作	本次访问到的顶点	`cnt`
0	否	`DFS(0)`	0, 1, 2	1
1, 2	是	跳过	—	1
3	否	`DFS(3)`	3, 4	2
4	是	跳过	—	2
5	否	`DFS(5)`	5, 6	3
6	是	跳过	—	3

连通分量数 = 3，生成森林三棵树的树边分别是 ${(0, 1), (1, 2)}$ 、 ${(3, 4)}$ 、 ${(5, 6)}$ ，共 4 条 $= n - k = 7 - 3$ ✓。

⚠️ 有向图上这条完全失效：一次 DFS 访问到的只是当前顶点能到达的顶点集合，既不是连通分量也不是强连通分量。两个反例——

$0 \to 1, 1 \to 2$ ：外层从 $i = 0$ 启动一次就访问完 3 个顶点，而强连通分量有 3 个。
$0 \to 1, 2 \to 1$ ：外层启动两次（ $i = 0$ 访问 ${0, 1}$ 、 $i = 2$ 访问 ${2}$ ），强连通分量仍是 3 个。

启动次数还依赖顶点编号：把第一个例子重新编号成 $2 \to 1, 1 \to 0$ ，外层就要启动 3 次。有向图求强连通分量要用专门的算法。

三色标记判有向环，以及为什么两种颜色不够

// 0: 未访问；1: 访问中（正在递归栈上）；2: 已完成
int color[MAX_VERTEX];

int hasCycle(int v) {
    color[v] = 1;                             // 进入递归栈
    for (int w = 0; w < n; w++) {
        if (G[v][w] != 1) continue;
        if (color[w] == 1) return 1;          // 指回了栈上的顶点 → 有环
        if (color[w] == 0 && hasCycle(w)) return 1;
    }
    color[v] = 2;                             // 退出递归栈
    return 0;
}

为什么两色不够：设有向图 $0 \to 1, 0 \to 2, 1 \to 2$ 。从 0 出发进 1，再从 1 进 2，回溯；回到 0 后检查邻居 2，发现它已被访问。若只有"访问过 / 没访问过"两种状态，这里会误判成有环——但这个图显然无环。关键区别是：顶点 2 此刻已经"完成"（不在递归栈上），不是"正在访问中"。只有指向仍在当前递归路径上的顶点，才构成环。

DFS 与 BFS 对照

对比维度	DFS	BFS	判别依据
辅助结构	栈（递归调用栈或显式栈）	队列	后进先出 → 深入；先进先出 → 逐层
策略	一条路走到底再回溯	一圈一圈向外扩散	看下一个访问的是"刚访问顶点的邻居"还是"最早入队顶点的邻居"
时间	邻接表 $O (n + e)$ 、邻接矩阵 $O (n^{2})$	完全相同	两者对边的访问次数一样
空间	$O (n)$ ，来自递归栈，最坏是链形图	$O (n)$ ，来自队列，最坏是星形图	量级同为 $O (n)$ ，但最坏情形的图形态相反
无权图最短路径	不能求	能求	BFS 的层数就是距离
生成树形状	细长	扁宽	由策略直接决定
典型应用	连通性、判环、逆拓扑排序、求路径	无权最短路径、层次划分、二部图判定	问题关心"能不能到"还是"最少几步到"

倒数第二行值得多说一句：DFS 求不了无权最短路径。它第一次到达某个顶点走的是"当前这条深入路径"，跟最短毫无关系。反例只要三个顶点： $0 - 1, 1 - 2, 0 - 2$ ，若 0 的链是 1 → 2，DFS 得到 $0 \to 1 \to 2$ 用了 2 条边，而 $0$ 到 $2$ 的真实距离是 1。求最短必须用 BFS。

考点速记

三条结论：

图遍历必须有 visited[]，且必须在访问顶点的同时置位——因为图里有环。
邻接矩阵 $O (n^{2})$ 、邻接表 $O (n + e)$ ，差别的根是"找邻接点要不要扫一整行"。
DFS 序列与生成树都不唯一；外层启动 DFS 的次数 = 无向图连通分量个数。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

数不同 DFS 序列的个数：给一个四顶点小有向图和固定起点，问从它出发能得到多少个不同的遍历序列。按起点的第一个分支分类逐支展开，别套排列数——某些分支会把后面的顶点顺带拖走，使那一支只贡献 1 种。
判某序列不是 DFS 序列：四个选项里三个合法、一个不合法。默认邻居的检查次序自由，逐个顶点核对"它能不能在此刻被访问到"。
改动输出位置后序列的性质：把输出语句移到退出递归前，在 DAG 上得到的是逆拓扑有序序列。四个选项通常是拓扑序 / 逆拓扑序 / BFS 序 / DFS 序，方向搞反就错。

易错：数 DFS 序列个数不能用排列数。 起点有 3 个邻居不等于 $3!$ 种——先进某个邻居时，它的后代会被一并访问掉，回到起点后可选分支变少了。

易错："输出移到退出递归前"得到的是逆拓扑序，不是拓扑序。 要变成拓扑序列还得整个反过来。

易错：判合法 DFS 序时，邻居检查次序是自由的。 按编号升序模拟一遍就否掉三个选项，是这类题的典型失分方式。

教材出处

严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p161，§6.5： "为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组 visited[n]"；同页 §6.5.1 给出 DFS 遍历过程的四步描述，并指出"深度优先搜索遍历类似于树的先序遍历，是树的先序遍历的推广"。
同书印刷 p162：DFS 递归算法（算法 6.3）与非连通图的 DFSTraverse（算法 6.4）；同页指出"图 6.17(b) 中所示的所有顶点加上标有实箭头的边，构成一棵以 $v_{1}$ 为根的树，称为深度优先生成树"。
同书印刷 p164：遍历的时间复杂度——"当用邻接矩阵存储时，时间复杂度为 $O (n^{2})$ ；用邻接表存储时，时间复杂度为 $O (n + e)$ "，且 DFS 与 BFS 同阶， "两种遍历方法的不同之处仅仅在于对顶点访问的顺序不同"。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.12，p364。

真题练习

2016Q62分 2015Q52分

深度优先搜索（DFS）

一条路走到黑，走不动了才退回岔口

先动手看一眼

两种存储结构下的实现

DFS 序列不唯一，以及怎么数有几个

生成树、非树边与判环

一处改动，DFS 变成逆拓扑排序

DFS 与 BFS 对照

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（2题）

深度优先搜索（DFS） ​

一条路走到黑，走不动了才退回岔口 ​

先动手看一眼 ​

两种存储结构下的实现 ​

DFS 序列不唯一，以及怎么数有几个 ​

生成树、非树边与判环 ​

一处改动，DFS 变成逆拓扑排序 ​

DFS 与 BFS 对照 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（2题）

深度优先搜索（DFS）

一条路走到黑，走不动了才退回岔口

先动手看一眼

两种存储结构下的实现

DFS 序列不唯一，以及怎么数有几个

生成树、非树边与判环

一处改动，DFS 变成逆拓扑排序

DFS 与 BFS 对照

考点速记

相关知识

真题练习