数据结构与算法 / 系统课时

深度优先搜索

深度优先搜索

深度优先搜索沿一条尚未探索完的路径持续深入,遇到无法继续的顶点后再回退。本课分别实现递归 DFS 与显式栈 DFS,并记录每个顶点的发现时间、完成时间和颜色状态。

学习目标

  • 理解 DFS 的深入、回退与完成时机。
  • 使用白、灰、黑三种状态区分未发现、处理中和已完成顶点。
  • 编写递归与显式栈版本,并验证两者产生一致的搜索轨迹。

知识导图

text
深度优先搜索
├── 状态
│   ├── WHITE:尚未发现
│   ├── GRAY:已发现但未完成
│   └── BLACK:邻接点已处理完
├── 实现
│   ├── 递归调用栈
│   └── 显式 Frame 栈
└── 时间记录
    ├── discover:进入顶点
    ├── finish:退出顶点
    └── 区间嵌套反映祖先关系

问题背景或应用场景

当任务需要完整探索一条分支后再回退时,DFS 比按层扩展更自然。典型应用包括连通分量、环检测、拓扑排序、强连通分量、迷宫回溯以及树和图上的子结构分析。

上一课的 BFS 使用队列保留“同一层”的待处理顶点;DFS 则使用调用栈或显式栈保留当前搜索路径。两种算法都能在 O(V+E)O(V+E) 时间内遍历邻接表图,但访问顺序和可直接获得的信息不同。

核心原理

顶点第一次进入搜索时从 WHITE 变为 GRAY,并记录发现时间;当它的所有邻接点都处理完后,从 GRAY 变为 BLACK,并记录完成时间。一个仍为 GRAY 的顶点位于当前递归路径上。

深度优先搜索的深入回退与时间区间

若顶点 u 是 DFS 森林中顶点 v 的祖先,则时间区间 [discover[u],finish[u]][discover[u], finish[u]] 会包含 [discover[v],finish[v]][discover[v], finish[v]]。这类区间关系常用于判断祖先、识别边类型和推导拓扑性质。

递归实现由语言运行时维护调用栈,代码简洁,但极深图可能导致栈溢出。显式栈实现可以避免递归深度限制,不过不能只保存顶点;若要准确模拟递归的完成时机,还应保存“下一个待扫描邻接点”的位置。

基础用法

递归 DFS 的关键步骤是:

  1. 进入顶点时记录发现时间并设为 GRAY。
  2. 依次访问所有仍为 WHITE 的邻接点。
  3. 所有邻接点处理完后设为 BLACK,再记录完成时间。

显式栈版本可使用 Frame(vertex, nextIndex) 保存一个尚未完成的调用帧。nextIndex 指向下一条待检查的邻接边;当它到达邻接表末尾时,才弹出栈并记录完成时间。这样得到的发现顺序、完成顺序和时间戳可以与递归版本一致。

对可能不连通的图,外层还要按顶点顺序检查所有 WHITE 顶点,并为每个未发现顶点启动一次 DFS,最终形成 DFS 森林。

完整可运行示例

下面的 Java 17 程序在同一有向图上执行递归 DFS 和显式栈 DFS,并比较发现顺序、完成顺序与时间戳。将代码保存为 DFSStateDemo.java。

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";
    }
}

编译并运行:

bash
javac DFSStateDemo.java
java DFSStateDemo

预期输出

text
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。正确做法是在外层循环中对每个未发现顶点启动新的搜索。

本课练习

  1. 在示例图中新增边 F-C,使用三色状态检测有向环;验收条件是扫描 F-C 时 C 仍为 GRAY。
  2. 修改显式栈实现,使其在不使用递归的情况下输出每棵 DFS 树的根,并支持不连通图。
  3. 根据完成时间实现拓扑排序,并在存在环时拒绝输出排序结果;对原示例图验证 A 位于 B 和 C 之前。

本课总结

  • DFS 通过调用栈或显式栈沿路径深入,并在邻接点全部处理后回退。
  • WHITE、GRAY、BLACK 与发现、完成时间共同描述了顶点的完整生命周期。
  • 显式栈若保存邻接扫描位置,就能准确复现递归 DFS 的进入和退出语义。

下一课预告

接下来将继续利用图遍历结果解决连通性、环检测和遍历树分析等问题,并比较不同图结构下的算法选择。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

深度优先搜索

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通