S03-X09 · 图论基础：遍历、最短路与拓扑排序

图算法代码都只有几十行，出错的地方几乎从不在循环写没写对，而在三个更靠前的位置：结构选错了、前提没验证、判据写少了。用邻接矩阵跑一万点的稀疏图、用 Dijkstra 处理负权、拓扑排序只看"队列空了"就宣布无环——三件事都能编译通过、跑出结果，再在某个数据上悄悄给出错误答案。

1. 三种表示：选错结构，后面全在补

// 邻接表：稀疏图的默认选择
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
// 边集：只存 {u, v, w}，供排序或反复全扫
int[][] edgeSet = edges.clone();

表示	空间	判邻接	全边扫描	适用面
邻接矩阵	O(V²)	O(1)	O(V²)	稠密图、点数小、Floyd、要 O(1) 查边
邻接表	O(V+E)	O(deg)	O(V+E)	稀疏图、绝大多数遍历与最短路
边集	O(E)	O(E)	O(E)	Bellman-Ford、Kruskal、需按权排序

判据只有一条：比较 E 与 V² 的量级。E 接近 V² 时 O(1) 判邻接才值钱；工程里绝大多数图是稀疏的，此时矩阵初始化本身就比整个算法贵——n = 10⁵ 的矩阵有 10¹⁰ 个格子，分配就过不去。head/next/to 链式前向星只是邻接表的紧凑版。

2. BFS 与 DFS：机制差异决定选型

int[] bfsDist(List<List<Integer>> g, int s) {
    int[] dist = new int[g.size()];
    Arrays.fill(dist, -1);                 // -1 既表示不可达，也兼作 visited
    Deque<Integer> q = new ArrayDeque<>();
    dist[s] = 0; q.add(s);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : g.get(u)) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1; q.add(v);   // 入队即定距
        }
    }
    return dist;
}

BFS 的队列保证按层推进：首次访问的距离即最短距离（边权全为 1 时层数就是距离）。DFS 的栈只是"一条路走到黑"，首次到达不代表最近。

需求	用哪个	原因
无权最短路 / 层数分层	BFS	首次到达即最短，队列天然按层
连通分量、岛屿计数	两者皆可	都要遍历整分量，选好写的
路径存在性、任意一条路径	DFS	找到即返回，不必展开整层
拓扑排序、环检测	DFS	后序 / 三色标记天然给顺序
找所有路径	DFS + 回溯	需要在栈上撤销状态

2.1 递归 DFS 的栈深度

递归深度等于当前路径长度，不是点数。链状图 n = 10⁵ 时深度即 10⁵；默认线程栈典型 512KB–1MB，按每帧几十到上百字节估算，通常数万层就 StackOverflowError。阈值随帧大小浮动，结论稳定：点数超过几万别用递归 DFS。

void dfsIterative(List<List<Integer>> g, int s) {
    boolean[] seen = new boolean[g.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(s);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (seen[u]) continue;
        seen[u] = true;
        for (int v : g.get(u)) if (!seen[v]) stack.push(v);   // 深度只受堆限制
    }
}

真正的错误是根本不标记：有环图直接死循环。

3. 拓扑排序：Kahn 与 DFS 后序

List<Integer> kahn(List<List<Integer>> g) {
    int n = g.size();
    int[] indeg = new int[n];
    for (List<Integer> adj : g) for (int v : adj) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    List<Integer> order = new ArrayList<>(n);
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);   // 入度归零才能排
    }
    if (order.size() != n) throw new IllegalStateException("有环");
    return order;
}

环判据是 order.size() != n，不是"队列变空"。有环时队列必然被抽空（环上点入度永远降不到 0），循环正常退出，只有长度能暴露问题；反之"每个点都有入度"也不等于有环——环及其下游都排不出去，长度差一定 ≥ 1。

DFS 后序反转必须三色标记：0 未访问、1 在栈上、2 已完成。遇 color[v] == 1 即回边 → 有环；完成时 push(u) 得到的就是逆拓扑序。

取舍：Kahn 迭代无栈风险、加边只改一个入度、天然给出"分批可执行任务"，输出顺序换优先队列还能求字典序最小；DFS 后序受递归深度限制、增量维护要重跑，但和递归结构一致。

4. Dijkstra：前提、两种实现、负权反例

正确性只依赖一个前提：边权非负。核心不变量"出堆即定终身"在负权下直接崩塌。

long[] dijkstra(List<List<int[]>> g, int s) {      // 元素 {to, weight}
    long[] dist = new long[g.size()];
    Arrays.fill(dist, Long.MAX_VALUE); dist[s] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
    pq.add(new long[]{0, s});
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        int u = (int) cur[1];
        if (cur[0] > dist[u]) continue;            // 丢弃过期条目
        for (int[] e : g.get(u)) {
            long nd = dist[u] + e[1];
            if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new long[]{nd, e[0]}); }
        }
    }
    return dist;
}

if (cur[0] > dist[u]) continue; 不是优化而是正确性的一部分：同一点会多次入堆，出堆时要丢弃陈旧副本。

取最小值有三种办法：数组线性扫描一轮 O(V)，总代价 O(V² + E)，适合稠密图与几百到几千个点；二叉堆（即上面的 PriorityQueue）O(log V)，总代价 O((V+E)·log V)，稀疏图的工程默认；斐波那契堆摊还 O(1)，总代价 O(E + V·log V)，理论最优但常数大。

负权反例，三点：s→b 权 1，s→a 权 2，b→a 权 -2，真实最短路 s→a = -1（经 b）。Dijkstra 先出堆 b(1)，再出堆 a(2) 并视为最终——此后 a 的 2 再也不会被改写，因为它已"小于等于任何未来路径"。结果 a = 2，全程不抛异常。

4.1 Bellman-Ford、SPFA 与 Floyd

long[] bellmanFord(int n, int[][] edges, int s) {   // edges = {u, v, w}
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE); dist[s] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean changed = false;
        for (int[] e : edges) {
            if (dist[e[0]] == Long.MAX_VALUE) continue;
            if (dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
        }
        if (!changed) break;                        // 提前收敛
    }
    for (int[] e : edges)                           // 第 n 轮仍松弛 → 有负环
        if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) throw new IllegalStateException("可达负环");
    return dist;
}

changed 提前退出是这里最值得加的两行：无负环的图通常前几轮就收敛。SPFA 是这个过程的队列版，只把被松弛过的点重新入队，期望接近 O(E)，但最坏仍是 O(V·E) 且极易被构造。结论：能上 Dijkstra 就别上 SPFA，需要负权直接用 Bellman-Ford。

Floyd 是 O(V³) 全源方案，k 必须在最外层——放最内层就退化成"只允许用 k 这一条中继"。规模上限是硬约束：V = 500 约 1.25×10⁸ 次内层循环，V = 2000 就到 8×10⁹。

5. 最小生成树与并查集

static final class DSU {
    private final int[] p, r;
    DSU(int n) { p = new int[n]; r = new int[n]; for (int i = 0; i < n; i++) p[i] = i; }
    int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }   // 路径压缩
    boolean union(int a, int b) {
        if ((a = find(a)) == (b = find(b))) return false;              // 已同集 → 成环
        if (r[a] < r[b]) { int t = a; a = b; b = t; }
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
}

维度	Prim	Kruskal
思路	从一点长树，每次取连接树内外的最小边	全局按权排序，逐条加入不成环的边
复杂度	O(E·log V)（堆）/ O(V²)（数组）	O(E·log E) + 并查集近 O(1)
适合	稠密图、邻接矩阵在手	稀疏图、边集在手
不连通	得到最小生成森林	靠 `used == n-1` 判定
实现前提	邻接表或矩阵	边集，必须可排序

并查集要路径压缩 + 按秩合并一起上：只用其一单次操作 O(log n)，两者兼备是摊还近 O(1)（α(n)）。

6. 排错：跑得通但答案错

现象	原因	处理
DFS 在链状大图上 `StackOverflowError`	递归深度 = 路径长度	改显式栈；调 `-Xss` 只是延后风险
DFS 死循环或结果错乱	忘 visited，或只在出栈时标记	访问时立刻标记，`seen` 与距离数组合并
Dijkstra 遇负权结果偏大	出堆即定终身的假设失效	有负权改 Bellman-Ford，先判负环
拓扑排序报了"有环"但其实无环	判据写成"队列为空"	判据只能是 `order.size() != n`
不可达点距离返回 0	`dist` 初始化为 0 而非 INF	初始化 `Long.MAX_VALUE`，松弛前判 INF
松弛后距离变负	`MAX_VALUE + w` 溢出	先判不可达再相加

最后一条最值得警惕：Integer.MAX_VALUE + 1 变成负数，"不可达"就被判成"发现了更短的路"，整张图结果塌掉。

7. 边界：什么规模就该换工具

场景	该用	不该做
V ≤ 500 且要全源	Floyd	跑 V 次 Dijkstra
稀疏图单源、非负权	Dijkstra + 二叉堆	邻接矩阵（分配就爆）
有负权、无负环	Bellman-Ford	SPFA 赌数据
需要判负环	Bellman-Ford 第 n 轮	Dijkstra（它没有负环这个概念）
无权最短路	BFS	Dijkstra（多一个 log，零收益）
动态连通性	并查集	每次重跑 DFS

另有一类常被误当图算法的问题：状态空间搜索，"状态"当点、"操作"当边，规模是状态数而非元素数。

8. 自测

10⁵ 点、2×10⁵ 条边的图为什么不能用邻接矩阵？
BFS 里"第一次访问即最短"依赖什么前提？边权改成 0 和 1 混合后该怎么修？
Kahn 实现里为什么"队列为空"不能作为无环判据？给出一个反例形状。
写出三点负权反例，说明 Dijkstra 在哪一步锁死了偏大的距离。
Kruskal 为什么必须用边集？union 返回 false 在算法里代表什么？
图不连通时，单源 Dijkstra 的返回值里哪些必须先判 INF？