拓扑排序与最短路入门

图论专题收尾篇。前两篇打好了建图、遍历和并查集的地基，这篇把三块常用武器一次补齐：淹岛法（遍历的直接应用）、拓扑排序（BFS 的经典应用）、Dijkstra（单源最短路）。

一、淹岛法：岛屿数量（200）与最大面积（695）

网格题的通用套路是"淹岛"：扫到一块没访问过的陆地，就启动 DFS/BFS 把整个连通块处理掉（标记 visited 或直接把 '1' 改成 '0' 沉掉），处理完计数 +1。

200. 岛屿数量的 DFS 版本：

public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);       // 淹掉整座岛
                count++;
            }
        }
    }
    return count;
}
 
private void dfs(char[][] grid, int i, int j) {
    // 越界或碰到水，直接返回
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
            || grid[i][j] != '1') return;
    grid[i][j] = '0';                  // 淹掉，防止重复访问
    dfs(grid, i + 1, j);               // 上下左右四个方向扩散
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

695. 岛屿的最大面积只需在淹岛的同时把岛的大小数出来：dfs 返回 1 + 四个方向的淹没结果之和。BFS 版本把递归换成队列，逐层扩散淹没，逻辑等价，网格很大时能避免递归栈溢出。

二、BFS 拓扑排序：Kahn 算法

思想

拓扑排序解决依赖关系问题：修课要先修先修课、编译要先编依赖包。把依赖建成有向边 A → B（A 是 B 的前置），拓扑排序就是给节点排一个序，保证每条边都从前面指向后面。

Kahn 算法的直觉：谁没有前置依赖（入度为 0），谁现在就能干。干完它，它指向的节点入度各减 1，又有新的"无依赖"节点浮现——用一个队列维护当前所有入度为 0 的节点即可：

算法流程：
1. 统计每个节点的入度，入度为 0 的节点全部入队
2. 出队一个节点，加入结果序；把它指向的所有节点入度 -1
3. 某节点入度减到 0 → 入队
4. 队列空了结束

207 / 210. 课程表

207 问"能否修完所有课"，210 还要输出一个可行顺序。Kahn 算法一步到位，两者只差"要不要记录出队顺序"：

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();   // 邻接表：edge[i] = i 指向的课
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]);   // 先修 p[1] 才能修 p[0]
        indegree[p[0]]++;            // p[0] 多一个前置
    }
 
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);        // 无前置的课先修
    }
 
    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        order[idx++] = cur;                          // 记录拓扑序
        for (int next : graph.get(cur)) {
            indegree[next]--;                        // 前置课修完
            if (indegree[next] == 0) queue.offer(next);
        }
    }
    // 判环：有环时环上节点入度永远减不到 0，出队数量 < 节点总数
    return idx == numCourses ? order : new int[0];
}

判环条件就藏在最后一句：如果图里有环，环上的节点互相等待、入度永远大于 0，最终出队的节点个数必然小于 n。207 只需把这个计数比较单独返回布尔值即可。

复杂度 O(V + E)：每个节点入队出队一次，每条边看一次。拓扑排序还有 DFS 染色实现（三色标记 + 逆后序），结果等价，Kahn 更好写不易错。

三、Dijkstra 单源最短路

问题与朴素版

给一个带正权有向图和源点 s，求 s 到每个点的最短距离。Dijkstra 的贪心策略：每轮从未确定的最短路集合外，挑 dist 最小的节点 u——它的距离已经不可能再被更短路径更新（因为别的路径都要经过更远的点），然后用 u 松弛它的邻居。

朴素实现 O(n²)：每轮线性扫描找最小 dist：

public int[] dijkstra(int n, int[][] edges, int s) {
    List<List<int[]>> graph = new ArrayList<>();     // graph[u] = [v, w] 列表
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) graph.get(e[0]).add(new int[]{e[1], e[2]});
 
    int[] dist = new int[n];
    boolean[] done = new boolean[n];                 // 是否已确定最短路
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;
 
    for (int round = 0; round < n; round++) {
        // 1. 在未确定节点中找 dist 最小的 u
        int u = -1;
        for (int i = 0; i < n; i++) {
            if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
        }
        if (u == -1 || dist[u] == Integer.MAX_VALUE) break;  // 剩余不可达
        done[u] = true;                              // 2. 确定它
        // 3. 用 u 松弛邻居：经过 u 中转是否更近
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    return dist;
}

优先队列优化（743. 网络延迟时间）

朴素版瓶颈在"找最小"的 O(n) 扫描，换成小顶堆后每轮 O(logE)。743 正是模板题：信号从节点 k 发出，问所有节点收到信号的最长时间——即以 k 为源跑 Dijkstra，答案是无穷距离（不可达则整体 -1）的最大值：

public int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
    for (int[] t : times) graph.get(t[0]).add(new int[]{t[1], t[2]});
 
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    // 堆中存 [当前距离, 节点]，按距离升序
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k});
 
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;          // 过期条目：已有更短的 dist，跳过
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;   // 有节点收不到
        ans = Math.max(ans, dist[i]);
    }
    return ans;
}

堆优化后复杂度 O((V + E) log V)，稠密图上与朴素版各有胜负，稀疏图上堆版明显占优。if (d > dist[u]) continue; 这个惰性删除技巧必须要有——同一节点可能被多次塞进堆，只认最早（最短）那条。

为什么不能有负权边

Dijkstra 的正确性建立在"确定一个点之后就不再回头"：它认定当前 dist 最小的点不会再被缩短。而负权边会打破这个前提——先走一条看起来更远的路，再经负边拉回，总距离反而更短，但该路径的中转点此前可能已被"确定"并跳过。

反例：s → a 权 2，s → b 权 3，b → a 权 -2
Dijkstra 先确定 a（dist=2），但真实最短是 s → b → a = 1
已确定的 a 不会再被更新 → 答案错误

遇到负权边就轮到 Bellman-Ford（对每条边做 V-1 轮松弛，允许"反悔"更新已确定的点，还能检测负权环）；要求任意两点间的距离则是 Floyd（三重循环 O(n³)，dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])）。选型口诀：无负权单源用 Dijkstra，有负权单源用 Bellman-Ford（SPFA 优化），多源小图用 Floyd。

四、易错点清单

淹岛法 DFS 在网格极大时会栈溢出，面试可主动提 BFS 替代。
Kahn 判环务必比较"出队计数与 n"，只看队列空是不够的。
建图方向别反：课程表里 prerequisites[i] = [课, 先修课]，边和入度都加在"课"上。
Dijkstra 松弛时 dist[u] + w 可能整型溢出，用 Integer.MAX_VALUE 作"无穷"时要先判 dist[u] 本身是否已达。
堆优化忘写"过期条目跳过"，复杂度退化为 O(E²)。
743 的答案取的是所有 dist 的最大值，不是 dist[n]。

五、LeetCode 题目清单

题号	题名	一句话考点
200	岛屿数量	淹岛法统计连通块个数
695	岛屿的最大面积	淹岛同时累加面积
690	员工的重要性	DFS/BFS 遍历带权值的树状结构
207	课程表	Kahn 算法判环：出队数是否为 n
210	课程表 II	拓扑序记录出队顺序
2115	从给定原材料中找到所有可制作的菜肴	拓扑排序思想统计可用数
743	网络延迟时间	Dijkstra 模板题，答案取 dist 最大值
1631	最小体力消耗路径	路径最大边权最小化，多解法对比
1334	阈值距离内邻居最少的城市	多次 Dijkstra 或 Floyd 统计
787	K 站中转内最便宜的航班	带限制的最短路，Bellman-Ford 变形

参考

代码随想录 · 图论专题