搜索算法：DFS、BFS 与拓扑排序

我对“搜索算法：DFS、BFS 与拓扑排序”的理解经历过一个从会背到会用的过程。其中最明显的一点是：我以前只会用“深度优先”和“广度优先”区分 DFS、BFS，却不会根据最短步数、依赖关系和内存成本来选。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。

搜索算法不是“会 DFS、会 BFS”这么简单。真正做题和做工程时，我们要先把问题抽象成状态图：一个状态是一个节点，一次合法变化是一条边。抽象清楚以后，DFS、BFS、拓扑排序就不是三套孤立模板，而是三种不同的状态推进方式。

它从哪里来

系统搜索与迷宫探索有相同直觉：深度优先沿一条路走到底，广度优先按距离一层层扩展。计算机图论把它们固化为栈或递归、队列两种框架；拓扑排序则把有向无环图中的先后依赖转化为可执行顺序。

先把问题变成图

图：DFS 适合路径探索，BFS 适合按层扩散，拓扑排序适合依赖关系

很多问题表面不是图，但本质都是图：

场景	节点	边
岛屿数量	一个格子	上下左右相邻陆地
单词接龙	一个单词	改一个字符后仍在词典中
课程表	一门课程	先修关系
迷宫最短路	一个坐标	向四个方向走一步
全排列	当前已选择集合	再选择一个未用元素

所以搜索题第一步不是写代码，而是问三个问题：

状态是什么？
状态之间如何转移？
我需要找任意解、所有解、最短步数，还是合法顺序？

DFS：沿着一条路径深入

DFS 适合处理路径、连通性、树形递归和回溯类问题。它的特点是先深入，再回退。

void dfs(int u, List<List<Integer>> graph, boolean[] visited) {
    visited[u] = true;
    for (int v : graph.get(u)) {
        if (!visited[v]) {
            dfs(v, graph, visited);
        }
    }
}

DFS 的核心不是递归本身，而是“进入状态”和“离开状态”的顺序。如果是普通遍历，进入后标记即可；如果是回溯，离开时还要撤销选择。

常见适用场景：

统计连通块数量。
判断图中是否存在路径。
枚举所有可能方案。
树的前序、中序、后序遍历。
检测有向图环路时维护递归栈。

DFS 的风险是递归深度。如果节点数量非常大，递归可能导致栈溢出，此时可以改成显式栈。

void dfsIterative(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : graph.get(u)) {
            if (!visited[v]) stack.push(v);
        }
    }
}

BFS：一层一层扩散

BFS 适合求无权图最短路径。因为它按层推进，第一次到达某个节点时，路径步数一定最少。

int bfs(int start, int target, List<List<Integer>> graph) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    dist[start] = 0;

    while (!queue.isEmpty()) {
        int u = queue.poll();
        if (u == target) return dist[u];
        for (int v : graph.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return -1;
}

BFS 通常要维护 dist，不要只用 visited。visited 只能说明来过，dist 还能说明第几层到达。

拓扑排序：按依赖关系安排顺序

拓扑排序只适用于有向无环图。它解决的不是最短路，而是“依赖谁先完成”的问题。

List<Integer> topoSort(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        indegree[e[1]]++;
    }

    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : graph.get(u)) {
            if (--indegree[v] == 0) queue.offer(v);
        }
    }
    return order.size() == n ? order : List.of();
}

如果最后结果数量小于节点数量，说明图中存在环，某些任务互相依赖，无法排出合法顺序。

复杂度

邻接表存图时，DFS、BFS、拓扑排序的时间复杂度通常都是 O(V + E)，其中 V 是节点数，E 是边数。空间复杂度主要来自图、访问数组和队列/栈。

我的分析

搜索题最容易写乱，是因为很多人上来就套 DFS 或 BFS。我的习惯是先写出“状态”和“转移”，再决定搜索方式。

要找所有路径，优先 DFS。
要找最少步数，优先 BFS。
要处理依赖先后，优先拓扑排序。
要剪枝枚举，DFS + 回溯。
要处理带权最短路，就不要硬用普通 BFS，而要进入 Dijkstra 或 Bellman-Ford。

面试题

为什么 BFS 能求无权图最短路？
DFS 如何判断有向图是否存在环？
拓扑排序结果不唯一是否正常？
邻接矩阵和邻接表对搜索复杂度有什么影响？
递归 DFS 在什么情况下需要改成迭代写法？