数据结构与算法 / 系统课时
深度优先搜索
深度优先搜索
深度优先搜索沿一条尚未探索完的路径持续深入,遇到无法继续的顶点后再回退。本课分别实现递归 DFS 与显式栈 DFS,并记录每个顶点的发现时间、完成时间和颜色状态。
学习目标
- 理解 DFS 的深入、回退与完成时机。
- 使用白、灰、黑三种状态区分未发现、处理中和已完成顶点。
- 编写递归与显式栈版本,并验证两者产生一致的搜索轨迹。
知识导图
深度优先搜索
├── 状态
│ ├── WHITE:尚未发现
│ ├── GRAY:已发现但未完成
│ └── BLACK:邻接点已处理完
├── 实现
│ ├── 递归调用栈
│ └── 显式 Frame 栈
└── 时间记录
├── discover:进入顶点
├── finish:退出顶点
└── 区间嵌套反映祖先关系问题背景或应用场景
当任务需要完整探索一条分支后再回退时,DFS 比按层扩展更自然。典型应用包括连通分量、环检测、拓扑排序、强连通分量、迷宫回溯以及树和图上的子结构分析。
上一课的 BFS 使用队列保留“同一层”的待处理顶点;DFS 则使用调用栈或显式栈保留当前搜索路径。两种算法都能在 时间内遍历邻接表图,但访问顺序和可直接获得的信息不同。
核心原理
顶点第一次进入搜索时从 WHITE 变为 GRAY,并记录发现时间;当它的所有邻接点都处理完后,从 GRAY 变为 BLACK,并记录完成时间。一个仍为 GRAY 的顶点位于当前递归路径上。

若顶点 u 是 DFS 森林中顶点 v 的祖先,则时间区间 会包含 。这类区间关系常用于判断祖先、识别边类型和推导拓扑性质。
递归实现由语言运行时维护调用栈,代码简洁,但极深图可能导致栈溢出。显式栈实现可以避免递归深度限制,不过不能只保存顶点;若要准确模拟递归的完成时机,还应保存“下一个待扫描邻接点”的位置。
基础用法
递归 DFS 的关键步骤是:
- 进入顶点时记录发现时间并设为
GRAY。 - 依次访问所有仍为
WHITE的邻接点。 - 所有邻接点处理完后设为
BLACK,再记录完成时间。
显式栈版本可使用 Frame(vertex, nextIndex) 保存一个尚未完成的调用帧。nextIndex 指向下一条待检查的邻接边;当它到达邻接表末尾时,才弹出栈并记录完成时间。这样得到的发现顺序、完成顺序和时间戳可以与递归版本一致。
对可能不连通的图,外层还要按顶点顺序检查所有 WHITE 顶点,并为每个未发现顶点启动一次 DFS,最终形成 DFS 森林。
完整可运行示例
下面的 Java 17 程序在同一有向图上执行递归 DFS 和显式栈 DFS,并比较发现顺序、完成顺序与时间戳。将代码保存为 DFSStateDemo.java。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class DFSStateDemo {
private static final String[] LABELS = {"A", "B", "C", "D", "E", "F"};
private static final int WHITE = 0;
private static final int GRAY = 1;
private static final int BLACK = 2;
private static final class Result {
private final List<Integer> discoveryOrder = new ArrayList<>();
private final List<Integer> finishOrder = new ArrayList<>();
private final int[] discover;
private final int[] finish;
private final int[] color;
private int time;
private Result(int vertexCount) {
discover = new int[vertexCount];
finish = new int[vertexCount];
color = new int[vertexCount];
}
}
private static final class Frame {
private final int vertex;
private int nextIndex;
private Frame(int vertex) {
this.vertex = vertex;
}
}
public static void main(String[] args) {
List<List<Integer>> graph = createGraph(LABELS.length);
addDirectedEdge(graph, 0, 1);
addDirectedEdge(graph, 0, 2);
addDirectedEdge(graph, 1, 3);
addDirectedEdge(graph, 2, 3);
addDirectedEdge(graph, 2, 4);
addDirectedEdge(graph, 3, 5);
addDirectedEdge(graph, 4, 5);
Result recursive = recursiveDfs(graph);
Result iterative = iterativeDfs(graph);
printResult("Recursive", recursive);
printResult("Iterative", iterative);
}
private static Result recursiveDfs(List<List<Integer>> graph) {
Result result = new Result(graph.size());
for (int vertex = 0; vertex < graph.size(); vertex++) {
if (result.color[vertex] == WHITE) {
visitRecursively(graph, vertex, result);
}
}
return result;
}
private static void visitRecursively(
List<List<Integer>> graph, int vertex, Result result) {
result.color[vertex] = GRAY;
result.discover[vertex] = ++result.time;
result.discoveryOrder.add(vertex);
for (int next : graph.get(vertex)) {
if (result.color[next] == WHITE) {
visitRecursively(graph, next, result);
}
}
// 只有所有邻接点都处理完,顶点才进入完成状态。
result.color[vertex] = BLACK;
result.finish[vertex] = ++result.time;
result.finishOrder.add(vertex);
}
private static Result iterativeDfs(List<List<Integer>> graph) {
Result result = new Result(graph.size());
Deque<Frame> stack = new ArrayDeque<>();
for (int start = 0; start < graph.size(); start++) {
if (result.color[start] != WHITE) {
continue;
}
discover(start, result);
stack.push(new Frame(start));
while (!stack.isEmpty()) {
Frame frame = stack.peek();
List<Integer> neighbors = graph.get(frame.vertex);
if (frame.nextIndex < neighbors.size()) {
int next = neighbors.get(frame.nextIndex++);
if (result.color[next] == WHITE) {
discover(next, result);
stack.push(new Frame(next));
}
} else {
stack.pop();
result.color[frame.vertex] = BLACK;
result.finish[frame.vertex] = ++result.time;
result.finishOrder.add(frame.vertex);
}
}
}
return result;
}
private static void discover(int vertex, Result result) {
result.color[vertex] = GRAY;
result.discover[vertex] = ++result.time;
result.discoveryOrder.add(vertex);
}
private static void printResult(String name, Result result) {
System.out.println(name + " discovery: "
+ formatVertices(result.discoveryOrder));
System.out.println(name + " finish: "
+ formatVertices(result.finishOrder));
System.out.println(name + " times:");
for (int vertex = 0; vertex < LABELS.length; vertex++) {
System.out.println(LABELS[vertex] + " = "
+ result.discover[vertex] + "/"
+ result.finish[vertex] + ", "
+ colorName(result.color[vertex]));
}
}
private static List<List<Integer>> createGraph(int vertexCount) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertexCount; i++) {
graph.add(new ArrayList<>());
}
return graph;
}
private static void addDirectedEdge(
List<List<Integer>> graph, int from, int to) {
graph.get(from).add(to);
}
private static String formatVertices(List<Integer> vertices) {
List<String> labels = new ArrayList<>();
for (int vertex : vertices) {
labels.add(LABELS[vertex]);
}
return String.join(" ", labels);
}
private static String colorName(int color) {
return color == BLACK ? "BLACK" : color == GRAY ? "GRAY" : "WHITE";
}
}编译并运行:
javac DFSStateDemo.java
java DFSStateDemo预期输出
Recursive discovery: A B D F C E
Recursive finish: F D B E C A
Recursive times:
A = 1/12, BLACK
B = 2/7, BLACK
C = 8/11, BLACK
D = 3/6, BLACK
E = 9/10, BLACK
F = 4/5, BLACK
Iterative discovery: A B D F C E
Iterative finish: F D B E C A
Iterative times:
A = 1/12, BLACK
B = 2/7, BLACK
C = 8/11, BLACK
D = 3/6, BLACK
E = 9/10, BLACK
F = 4/5, BLACK显式栈保存了每个顶点的邻接扫描位置,因此它与递归版本在同一邻接顺序下得到一致结果。若只把邻接点一次性全部压栈,发现顺序可能改变,而且无法自然确定每个顶点的完成时刻。
Tips
- 递归 DFS 适合深度可控、可读性优先的场景;图可能形成很长链时优先考虑显式栈。
- 邻接表顺序会影响 DFS 森林形态和时间戳,但不会影响是否能访问到某个顶点。
- 在有向图中扫描到
GRAY邻接点通常意味着存在返回当前搜索路径的边,可用于环检测。 - 需要拓扑排序时,应在顶点完成时加入结果,最后反转完成顺序。
常见错误
1. 只有布尔访问标记
单一 visited 只能区分“见过”和“没见过”,无法区分正在处理与已经完成。环检测或边分类需要至少三种状态。
2. 显式栈只保存顶点
简单地弹出顶点后立即把所有邻接点压栈,虽然仍可能完成遍历,但无法准确模拟递归的退出时机。要记录完成时间,应保存 nextIndex 或使用进入、退出两类事件。
3. 只从编号 0 启动一次
不连通图中,其余连通分量会保持 WHITE。正确做法是在外层循环中对每个未发现顶点启动新的搜索。
本课练习
- 在示例图中新增边 F-C,使用三色状态检测有向环;验收条件是扫描 F-C 时 C 仍为
GRAY。 - 修改显式栈实现,使其在不使用递归的情况下输出每棵 DFS 树的根,并支持不连通图。
- 根据完成时间实现拓扑排序,并在存在环时拒绝输出排序结果;对原示例图验证 A 位于 B 和 C 之前。
本课总结
- DFS 通过调用栈或显式栈沿路径深入,并在邻接点全部处理后回退。
WHITE、GRAY、BLACK与发现、完成时间共同描述了顶点的完整生命周期。- 显式栈若保存邻接扫描位置,就能准确复现递归 DFS 的进入和退出语义。
下一课预告
接下来将继续利用图遍历结果解决连通性、环检测和遍历树分析等问题,并比较不同图结构下的算法选择。