图算法：遍历、最短路、MST、拓扑与 Tarjan

图由顶点和边组成，是描述"关系"最自然的数据结构。本文覆盖图的存储、BFS/DFS 搜索、Dijkstra/Bellman-Ford 最短路径、Prim/Kruskal 最小生成树和拓扑排序，每个算法配有过程图辅助理解。

目录

章节	说明
图的基本概念	顶点、边、有向/无向/带权图
图的存储	邻接矩阵 vs 邻接表
BFS 广度优先搜索	逐层扩散，保证最短路径
DFS 深度优先搜索	沿路走到底，回溯换路
连通分量与并查集	遍历整张图、合并组件与网格建模
强连通分量（SCC）	有向图的双向可达与 Tarjan 模板
无向图的桥（关键连接）	dfn/low 判定割边，LeetCode 1192
最短路径	Dijkstra / Bellman-Ford
最小生成树	Prim / Kruskal
拓扑排序	有向无环图的线性排序
图题解题决策框架	看到一道图题，如何判断用哪个算法

图的基本概念

图（Graph） 由顶点（Vertex） 和边（Edge） 组成，顶点可以与任意其他顶点建立连接关系。

概念	说明	示例
无向图	边没有方向，A-B 等价于 B-A	微信好友关系
有向图	边有方向，A→B 不等于 B→A	微博关注关系
带权图	每条边有权重	地图路程、网络延迟
度（Degree）	与某顶点相连的边数	无向图
入度（In-degree）	指向该顶点的边数	有向图
出度（Out-degree）	从该顶点出发的边数	有向图
稀疏图	顶点多，边少（E ≪ V²）	社交网络
稠密图	边数接近 V²	全连接网络

图的存储

同一张图可以用邻接矩阵或邻接表存储，二者的空间和时间取舍截然不同：

邻接矩阵

用二维数组 A[V][V] 存储，A[i][j] 表示顶点 i 到顶点 j 的边权（无边时为 0 或 ∞）：

int[][] graph = new int[V][V];
// 无向图：双向赋值
graph[i][j] = 1;
graph[j][i] = 1;
// 带权图：存权重
graph[i][j] = weight;

优点	缺点
查询两点关系 O(1)	空间 O(V²)，稀疏图严重浪费
矩阵运算方便（Floyd-Warshall 等）	无向图存储冗余（天然对称矩阵）

邻接表

每个顶点对应一个链表，只存储实际存在的邻居：

public class Graph {
    private final int v;
    private final LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) adj[i] = new LinkedList<>();
    }

    public void addEdge(int s, int t) { // 无向图
        adj[s].add(t);
        adj[t].add(s);
    }
}

优点	缺点
空间 O(V+E)，稀疏图节省	查询两点关系需遍历链表 O(度数)
适合大规模稀疏图	随机访问对 CPU 缓存不友好

升级版邻接表：将链表替换为红黑树、跳表或散列表，提升查询效率。如微博关注关系用跳表还能支持按用户名排序分页。

选型对比

维度	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
查询两点关系	O(1)	O(度数)
遍历所有邻居	O(V)	O(度数)
适用场景	稠密图、矩阵运算	稀疏图（社交网络）

BFS 广度优先搜索

广度优先搜索（BFS） 用队列驱动，从起点向外逐层扩散，先访问距离为 1 的邻居，再访问距离为 2 的……

关键性质：BFS 找到的路径是边数最少的路径（无权图的最短路径）。

为什么逐层扩散就保证最短？ BFS 按"距起点的边数"分层扩散：先访问距起点 1 条边的所有点，再 2 条边……当某节点第一次被访问时，它一定是从起点出发走"恰好 N 条边"首次到达，这个 N 就是它的最短边数。队列的 FIFO 保证"先被发现的点距离不会更大"——这是 BFS 能保证最短、而 DFS 不能的根本原因（DFS 一路深扎，第一次到达某点走的可能是条长绕路）。

识别信号：题目问"最少几步""最少操作次数""最短路径"且每步代价相同 → 优先 BFS。若每步代价不同（带权）则改用 Dijkstra。

实现

public void bfs(int s, int t) {
    if (s == t) return;
    boolean[] visited = new boolean[v];
    int[] prev = new int[v];         // prev[i] = 到达 i 的前驱节点
    Arrays.fill(prev, -1);

    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty()) {
        int w = queue.poll();
        for (int q : adj[w]) {
            if (!visited[q]) {
                prev[q] = w;
                if (q == t) {
                    printPath(prev, s, t); // 找到目标，打印路径
                    return;
                }
                visited[q] = true;
                queue.add(q);
            }
        }
    }
}

private void printPath(int[] prev, int s, int t) {
    if (prev[t] != -1 && t != s) printPath(prev, s, prev[t]);
    System.out.print(t + " ");
}

三个辅助变量的作用：

变量	作用
visited[]	标记已访问，防止重复入队
queue	FIFO 保证按层处理
prev[]	反向记录路径，最后递归还原

复杂度

维度	复杂度	原因
时间	O(V+E)	每个顶点和每条边最多访问一次
空间	O(V)	visited、queue、prev 均为线性

DFS 深度优先搜索

深度优先搜索（DFS） 沿一条路走到底，走不通则回溯换路，本质上是递归调用栈的深度优先遍历。

关键性质：DFS 找到的路径不保证是最短路径，但能遍历图中所有可达顶点。

适用场景：DFS 的"走到尽头再回溯"特性，特别适合需要"探到底"的问题——连通性判断、环检测、拓扑排序、找割点/桥/SCC、回溯搜索所有方案。凡是要遍历整张图、不在意路径长度的，DFS 比 BFS 更省内存（只存当前路径栈，不像 BFS 要存整层）。

识别信号：问"是否连通/有环/能到达""所有方案""关键边或点"→ DFS；问"最少几步"→ BFS。

DFS 的边分类

DFS 走完一张图，所有边分四类（以有向图为完整框架）：

边类型	指向的节点与 u 的关系	是否树边
树边（tree）	u → 未访问的子节点	是
回边（back）	u → u 的祖先	否
前向边（forward）	u → u 的后代，但不是当初发现该后代的那条边	否
横叉边（cross）	u → 既非祖先也非后代的已访问节点	否

树边 vs 前向边：都指向后代，区别在"是不是 DFS 用来发现该后代的那条边"。树边是 v 未访问时第一次发现 v 的边；前向边是 v 已访问后、又一条通向该后代的冗余边。例：有向边 A→B、B→C、A→C，DFS 从 A：A→B（树边）、B→C（树边）、A→C（C 已是后代 → 前向边）。前向边指向的后代 dfn 比自己大，对 low 无贡献，算法上常忽略。

横叉边：连接两个没有祖孙关系的已访问节点，只存在于有向图。例：有向边 A→B、A→C、C→B，DFS 从 A：A→B（树边）、A→C（树边）、C→B（B 在另一子树且已访问 → 横叉边）。

为什么无向图只有树边和回边？ 无向边是双向的。当 DFS 在 u 发现邻居 v 已访问、且 v 不是 u 的父亲时，v 一定是 u 的祖先——若 v 是个已访问完的平行节点，v 当初被访问时沿 v-u 这条无向边早该走到 u、把 u 纳入 v 的子树；既然 u 在 v 之后才被访问，u 必是从 v 那条路下来的，v 是祖先。所以无向图没有前向边和横叉边。

这正是 Tarjan 在无向图成立的前提：边只有树边和回边两类，low 更新才简化成三条规则——遇到已访问邻居直接当回边处理。而有向图求 SCC 时横叉边会添乱，需用 inStack 把它排除。

实现

private boolean found = false;

public void dfs(int s, int t) {
    boolean[] visited = new boolean[v];
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    recurDfs(s, t, visited, prev);
    if (found) printPath(prev, s, t);
}

private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
    if (found) return;
    visited[w] = true;
    if (w == t) { found = true; return; }
    for (int q : adj[w]) {
        if (!visited[q]) {
            prev[q] = w;
            recurDfs(q, t, visited, prev);
        }
    }
    // 此处隐式回溯：从 w 的所有邻居返回后，w 标记已访问但不影响其他路径
}

复杂度

维度	复杂度
时间	O(E)（每条边最多访问两次）
空间	O(V)（visited 数组 + 递归调用栈）

BFS vs DFS 对比

维度	BFS	DFS
驱动结构	队列（显式）	调用栈（隐式递归）
路径保证	最短路径（边数最少）	不保证最短
内存占用	较大（层宽可能很大）	较小（只存当前路径）
典型应用	最短路径、层序遍历、社交网络N度好友	拓扑排序、连通分量、回溯搜索

连通分量与并查集

连通分量（Connected Component）是无向图中“任意两个点都能互相到达”的最大顶点集合。单次 BFS/DFS 只能覆盖一个起点可达的组件；遍历所有未访问顶点，每启动一次搜索，组件数加一。

用 DFS / BFS 计数

int countComponents(List<Integer>[] graph) {
    boolean[] visited = new boolean[graph.length];
    int components = 0;
    for (int i = 0; i < graph.length; i++) {
        if (!visited[i]) {          // 发现一个尚未覆盖的新组件
            components++;
            dfsMark(graph, i, visited);
        }
    }
    return components;
}

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

时间复杂度为 O(V + E)：每个顶点仅标记一次，每条边最多检查两次。BFS 只需把 dfsMark 换成队列版本，计数逻辑不变。

并查集：动态合并组件

当边持续加入、需要反复判断“两个点是否已连通”时，并查集比每次重新遍历更合适。count 初始为顶点数；一次成功的 union 将两个组件合并，count--。

class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        count--;
        return true;
    }

    int count() { return count; }
}

选择：静态图求一次组件数，用 DFS/BFS；边不断加入、需要快速连通性查询，用并查集。路径压缩与按大小合并后，并查集单次操作的均摊复杂度近似 O(1)。

并查集的 API、复杂度直觉、带权/可撤销等扩展见 并查集；本节聚焦它在图连通性中的使用。

网格图：岛屿数量

二维网格可看成图：每个陆地格是顶点，上下左右相邻的陆地之间有边。LeetCode 200 的关键是每发现一块未访问陆地就计数一次，并用 DFS 将整座岛标记为水。

int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;
                flood(grid, r, c);
            }
        }
    }
    return count;
}

void flood(char[][] grid, int r, int c) {
    if (r < 0 || r == grid.length || c < 0 || c == grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0';
    flood(grid, r + 1, c); flood(grid, r - 1, c);
    flood(grid, r, c + 1); flood(grid, r, c - 1);
}

题目	平台	建模与模板
547. 省份数量	LeetCode	邻接矩阵 + DFS / 并查集计数
200. 岛屿数量	LeetCode	网格图 + DFS / BFS 染色
1319. 连通网络的操作次数	LeetCode	并查集组件数 + 冗余边

有向图的“强连通分量”要求任意两点可以双向到达，需用 Tarjan 或 Kosaraju；它是本节无向连通分量的进阶主题。

强连通分量（SCC）

在有向图中，普通“从 A 能到 B”不代表 B 能回到 A。强连通分量（Strongly Connected Component, SCC）是一个极大的顶点集合：集合内任意两点都能沿有向边互相到达。

将每个 SCC 缩成一个点后，得到的“缩点图”一定是 DAG；这使得课程依赖、调用环、控制流分析等问题可以先识别环，再在 DAG 上做拓扑排序或 DP。

Tarjan 算法：一次 DFS 找出所有 SCC

为什么有向图求 SCC 不能简单 DFS？普通 DFS 只能判断"A 能到 B"，但 SCC 要求双向可达，而 DFS 树的方向是固定的。Tarjan 的精妙之处在于三个观察叠加：

观察一：SCC 在 DFS 树上是一段连续子树。 一个 SCC 内所有节点互相可达，DFS 必然从其中一个节点进入并遍历完整个 SCC 才会回溯——因此一个 SCC 对应 DFS 树上一棵子树，其根是该 SCC 中 dfn 最小的节点。

观察二：根的 low == dfn。 SCC 的根是组内最早被访问的，它的子树（含回边）怎么走都跑不出这个 SCC，所以 low[u] == dfn[u] 就是根的标志。反之 low[u] < dfn[u] 说明 u 能到达更早的祖先，u 不是根，它的 SCC 要等那个祖先弹栈时一并弹出。

观察三：栈只留"待定"节点。 已确定为完整 SCC 的节点出栈后，不能再被回边连回去（它们已闭合）。所以回边更新 low 时只认仍在栈中的祖先（inStack[v]），否则会把别的 SCC 的节点错误拉进来。

三者结合得到 Tarjan 的状态定义与弹栈时机：

状态	含义
dfn[u]	u 第一次被 DFS 访问的时间
low[u]	从 u 出发、经过 DFS 子树和至多一条回边，能到达的最小 dfn
inStack[u]	u 是否仍在当前 DFS 路径栈中（待定 SCC）

当 low[u] == dfn[u]：u 是其 SCC 的根，从栈顶弹到 u，弹出的所有节点构成一个完整 SCC。

class TarjanScc {
    private final List<Integer>[] graph;
    private final int[] dfn, low;
    private final boolean[] inStack;
    private final Deque<Integer> stack = new ArrayDeque<>();
    private int time = 0;
    private int sccCount = 0;

    TarjanScc(List<Integer>[] graph) {
        this.graph = graph;
        int n = graph.length;
        dfn = new int[n];
        low = new int[n];
        inStack = new boolean[n];
    }

    int count() {
        for (int u = 0; u < graph.length; u++) {
            if (dfn[u] == 0) tarjan(u);
        }
        return sccCount;
    }

    private void tarjan(int u) {
        dfn[u] = low[u] = ++time;
        stack.push(u);
        inStack[u] = true;
        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]); // DFS 树边
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]); // 指向栈内祖先的回边
            }
        }
        if (low[u] == dfn[u]) {
            sccCount++;
            while (true) {
                int v = stack.pop();
                inStack[v] = false;
                if (v == u) break;
            }
        }
    }
}

⚠️ 更新 low[u] 时，只有 v 仍在栈内才可使用回边；已出栈的节点属于已确定的其他 SCC，不能把它们混入当前组件。

无向图的桥（关键连接）

桥是边的性质，不是点的性质。 无向边 (u, v) 若删除后使连通分量数量增加，它就是桥；等价地，这条边不属于任何环。

这正是 LeetCode 1192「查找集群内的关键连接」所求的对象。注意：不能只找”不在环上的节点”——两个环之间的一条连接边仍是桥，但它的两个端点都可能在各自的环上。下面由简入深，一步步推出 Tarjan 的判定。

第一步：暴力思路与它的代价

最直白的做法：枚举每条边，删掉它后跑一次 DFS/BFS 看连通分量是否变多。一次判断 O(V+E)，枚举 E 条边共 O(E·(V+E))，n=10⁵ 时必超时。

Tarjan 的目标：只跑一次 DFS 就找出所有桥。关键在于 DFS 会把图变成一棵树，从而把边分成两类。

第二步：DFS 把图变成树

从任一节点出发做 DFS，走过的边分为两类：

边的类型	含义	在 DFS 中的角色
树边（tree edge）	DFS 真正向下递归走过的边	构成 DFS 生成树
回边（back edge）	指向已访问过的祖先的边	不在树上的”捷径”

无向图中，已访问的非父邻居一定是祖先（不存在横叉边，详见 DFS 的边分类），这是 Tarjan 成立的前提。

graph TD
    A((A)) -->|树边| B((B))
    B -->|树边| C((C))
    C -->|树边| D((D))
    C -.->|回边| A
    linkStyle 3 stroke:#e88,stroke-dasharray:5 5

回边是桥的天敌：一条边是桥，意味着它所在的子树没有任何回边能绕开它通往上方。于是问题转化为——“v 的子树里有没有回边能连到 u 或 u 的祖先？”

第三步：两个时间戳 dfn 与 low

数组	含义
dfn[u]	u 第一次被 DFS 访问的时间戳（全局递增）
low[u]	从 u 出发，沿 DFS 子树往下走、至多再走一条回边，能到达的最小 dfn

low[u] 直觉上就是”u 的子树能攀到的最高祖先的 dfn”。若 low[u] 很小，说明 u 这一支有回边通往很靠上的祖先，根子扎得深。

第四步：low 的三条更新规则

场景	更新操作	说明
初始化	low[u] = dfn[u] = ++time	自己只能到自己
树边 u→v	dfs(v) 返回后 low[u] = min(low[u], low[v])	子树的 low 传递上来
回边 u→w	low[u] = min(low[u], dfn[w])	能直接攀到祖先 w

⚠️ 回边更新用 dfn[w] 而非 low[w]：回边只算”一条”捷径，不能把 w 子树里别的回边也捎带过来。

第五步：桥的判定条件

对树边 (u, v)（u 是 v 的父亲）：

low[v] > dfn[u] ⟺ (u, v) 是桥

直觉证明：想象删掉边 (u, v)。v 的子树（v 及其所有后代）若不想被孤立、还能连到子树之外的部分（u 及 u 的祖先），只能靠回边——无向图 DFS 里从子树通往上方祖先的边只有回边这一种（见 DFS 的边分类）。low[v] 记录的正是 v 子树通过回边能到达的最高祖先的 dfn：

• low[v] > dfn[u]：v 子树够不到 u 和 u 的祖先，出路只有 (u, v) 这一条 → 是桥。
• low[v] ≤ dfn[u]：存在回边从 v 子树连回 u 或更高处，删掉 (u, v) 仍连通 → 不是桥。

第六步：与割点的区别（只差一个等号）

判定	割点（关节点）	桥
条件	low[v] >= dfn[u]	low[v] > dfn[u]
为何不同	回边连回 u 自身时，u 被删照样断子树	回边连回 u 自身时，边 (u,v) 没删，子树仍可达 u

即 low[v] == dfn[u] 时：回边直接搭到 u，所以 (u, v) 不是桥，但 u 仍是割点。此外根节点对桥无需特殊处理（不像割点要数根有几个孩子）。

与 SCC 版 Tarjan 的区别

维度	SCC（有向图）	桥（无向图）
目标	找互相可达的点集	找删除后会断开的边
low 的用途	判断 low[u] == dfn[u]，弹栈形成 SCC	对 DFS 树边判断 low[v] > dfn[u]
栈 / inStack	需要，维护尚未归属 SCC 的节点	不需要
父边	无此特殊处理	必须跳过进入当前节点的那条父边

Java 模板：寻找所有桥

题目保证没有重边，因此用父节点 parent 跳过父边即可。若允许重边，应改为记录边编号并只跳过进入当前节点的那一条边。

class TarjanBridge {
    private final List<Integer>[] graph;
    private final int[] dfn;
    private final int[] low;
    private final List<List<Integer>> bridges = new ArrayList<>();
    private int time;

    TarjanBridge(List<Integer>[] graph) {
        this.graph = graph;
        dfn = new int[graph.length];
        low = new int[graph.length];
    }

    List<List<Integer>> findBridges() {
        for (int u = 0; u < graph.length; u++) {
            if (dfn[u] == 0) {
                dfs(u, -1);
            }
        }
        return bridges;
    }

    private void dfs(int u, int parent) {
        dfn[u] = low[u] = ++time;
        for (int v : graph[u]) {
            if (v == parent) {
                continue; // 无向边会在邻接表中出现两次，跳过父边的反向记录
            }
            if (dfn[v] == 0) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]); // DFS 树边
                if (low[v] > dfn[u]) {
                    bridges.add(Arrays.asList(u, v));
                }
            } else {
                low[u] = Math.min(low[u], dfn[v]); // 指向祖先的回边
            }
        }
    }
}

完整示例：LeetCode 1192

n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]：三角形 0-1-2 上挂一个叶子 3。从 0 开始 DFS，树边为 0-1、1-2、1-3，回边为 2-0。

graph TD
    N0["0<br/>dfn=1, low=1"] --> N1["1<br/>dfn=2, low=1"]
    N1 --> N2["2<br/>dfn=3, low=1"]
    N2 -.-> N0
    N1 --> N3["3<br/>dfn=4, low=4"]
    style N3 fill:#fcc,stroke:#c00,stroke-width:2px
    linkStyle 2 stroke:#e88,stroke-dasharray:5 5
    linkStyle 3 stroke:#c00,stroke-width:3px

逐节点计算 dfn / low：

节点	dfn	low	计算过程
0	1	1	起点
1	2	1	被 0 访问
2	3	1	回边 2-0 → low[2] = min(3, dfn[0]=1) = 1
3	4	4	叶子，无回边

逐条判定树边：

树边	判定	是否桥
(0,1)	low[1]=1 > dfn[0]=1 ?	否
(1,2)	low[2]=1 > dfn[1]=2 ?	否（有回边绕开）
(1,3)	low[3]=4 > dfn[1]=2 ?	是

答案 1,3，与题目一致。

时间复杂度为 O(V + E)，空间复杂度为 O(V)。Java 的递归 DFS 在退化链上可能达到 10^5 层； 若运行环境栈较小，需要改为显式栈模拟 DFS；后序、回溯或需要回传子结果的算法，则应把调用帧与恢复阶段都显式建模，见 显式栈与状态机替代递归。

阅读顺序

1. 先在纸上画出一个三角形外接一条尾边，手动写出每个节点的 dfn 与 low。
2. 对照模板理解两处 low 更新：子节点返回后取 low[v]，遇到已访问的祖先时取 dfn[v]。
3. 最后阅读 cp-algorithms 的桥算法文章，它给出了判定的推导和完整参考实现。

Tarjan 与 Kosaraju

算法	核心做法	时间 / 空间	适合
Tarjan	一次 DFS + 栈 + dfn/low	O(V+E) / O(V)	常用模板，单图遍历
Kosaraju	原图 DFS 完成时间 + 反图 DFS	O(V+E) / O(V+E)	已方便构造反图时，直觉更直接

题目	平台	核心
2360. 图中的最长环	LeetCode	功能图中的环与访问时间
1192. 查找集群内的关键连接	LeetCode	同用 dfn/low，但寻找桥而非 SCC
802. 找到最终的安全状态	LeetCode	反图拓扑，理解环与 DAG

最短路径

Dijkstra 算法

适用于无负权边的带权图，求单源最短路径。

核心思路：贪心。维护 dist[] 数组记录起点到每个顶点的当前最短距离，每次从未处理的顶点中取 dist 最小的，用它松弛所有邻居。

为什么贪心是对的？ 取出 dist 最小的未处理点 u 时，u 的距离已不可能再变小——任何其他未处理点的 dist 都 ≥ u，经过它们绕到 u 只会更长（边权非负）。所以 u 的最短路此时就被"锁定"，标记为已处理不再动。这也解释了为何有负权就失效：若存在负权边，绕路反而更短，"dist 最小即确定"的假设不成立，贪心提前锁定会错过更短的负权绕行。

识别信号：单源、带权、无非负权 → Dijkstra；"最短时间/距离"且无负权时优先它。

松弛操作：若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]。

public int[] dijkstra(int src) {
    int[] dist = new int[v];
    boolean[] processed = new boolean[v];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // 优先队列：(distance, vertex)
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[1];
        if (processed[u]) continue;
        processed[u] = true;

        for (int[] edge : adjWeighted[u]) { // [neighbor, weight]
            int neighbor = edge[0], weight = edge[1];
            if (dist[u] + weight < dist[neighbor]) {
                dist[neighbor] = dist[u] + weight;
                pq.offer(new int[]{dist[neighbor], neighbor});
            }
        }
    }
    return dist;
}

实现	时间复杂度	说明
朴素实现（线性扫描）	O(V²)	适合稠密图
优先队列优化	O((V+E) log V)	适合稀疏图

Bellman-Ford 算法

适用于有负权边的图，可检测负权环。

核心思路：对所有边做 V−1 轮松弛。第 k 轮结束后，dist[v] 是从源点经过至多 k 条边的最短距离。若第 V 轮仍能松弛，说明存在负权环。

为什么是 V−1 轮？ 一条最短路径若是简单路径（不含环），最多经过 V−1 条边——只有 V 个顶点，第 V 条边必然回到已访问过的点形成环。最短路不会含正权环（绕了更长无意义），但可能含负权环（可无限绕短）。所以 V−1 轮松弛足以传播完所有简单最短路；若第 V 轮还能松弛，说明最短路里掺了负权环（可以一直绕下去变短），据此检测。

识别信号：图中有负权边，或需检测负权环（如"汇率套利""能否无限变短"）→ Bellman-Ford。

public int[] bellmanFord(int src) {
    int[] dist = new int[v];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int i = 0; i < v - 1; i++) {        // V-1 轮
        for (int[] edge : edges) {            // 遍历所有边 (u, v, w)
            int u = edge[0], nv = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[nv])
                dist[nv] = dist[u] + w;
        }
    }
    // 检测负权环：若第 V 轮仍能松弛则有负权环
    for (int[] edge : edges) {
        if (dist[edge[0]] + edge[2] < dist[edge[1]])
            throw new RuntimeException("存在负权环");
    }
    return dist;
}

最短路径算法对比

算法	负权边	负权环检测	时间复杂度	适用场景
Dijkstra	✗	✗	O((V+E) log V)	地图导航、无负权
Bellman-Ford	✓	✓	O(VE)	货币套利检测、有负权
Floyd-Warshall	✓	✓	O(V³)	全源最短路径（V 较小）

最小生成树

最小生成树（MST）：在连通无向带权图中，找一棵包含所有 V 个顶点、仅用 V−1 条边、且边权之和最小的树。

贪心为什么正确：切边定理

Prim 和 Kruskal 都是贪心，能保证正确靠的是同一条定理——切边定理（Cut Property）：

把顶点集任意切成 S 和 V−S 两部分，横跨两部分的最短边一定属于某棵最小生成树。

直觉：假设最短横跨边 e 不在 MST 里，那 MST 必有另一条横跨边 f 连接 S 和 V−S；用 e 替换 f，总权更小且不形成环（e、f 都横跨同一刀，换掉不破坏连通），矛盾。所以 e 必在 MST 中。

两个算法都是在反复"切一刀、取最短横跨边"：

算法	怎么切	取哪条
Prim	S = 已选点集，V−S = 未选点集	这刀的最短横跨边
Kruskal	按边权排序，加的边连接两个当前不在同一连通分量的点	相当于切那两个分量，取最短横跨边

识别信号："用最小代价把所有点连成连通""联网""连接所有城市" → MST。稠密图（E≈V²）选 Prim，稀疏图选 Kruskal（排序主导，O(E log E)）。

Prim 算法

思路：从任意顶点出发，维护"已选集合 S"，每次选择连接 S 与非 S 的最小权边，将新顶点并入 S，重复 V−1 次。

S = {start}
重复 V-1 次：
  在所有 (u, v) 边中，u ∈ S，v ∉ S，选权重最小的边
  将 v 加入 S，记录边 (u, v)

• 时间：O(V²)，优先队列优化后 O((V+E) log V)
• 适合稠密图（E ≈ V²，优先队列优势不明显）

Kruskal 算法

思路：将所有边按权重从小到大排序，依次考察每条边——若加入后不形成环，则纳入 MST。用并查集判断成环。

public List<int[]> kruskal(int v, int[][] edges) {
    // edges: [u, v, weight]，按 weight 排序
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    int[] parent = new int[v];
    for (int i = 0; i < v; i++) parent[i] = i;

    List<int[]> mst = new ArrayList<>();
    for (int[] edge : edges) {
        int pu = find(parent, edge[0]);
        int pv = find(parent, edge[1]);
        if (pu != pv) {           // 不在同一连通分量，不成环
            mst.add(edge);
            parent[pu] = pv;      // 合并并查集
        }
        if (mst.size() == v - 1) break;
    }
    return mst;
}

private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]); // 路径压缩
    return parent[x];
}

• 时间：O(E log E)（排序主导）
• 适合稀疏图

Prim vs Kruskal

维度	Prim	Kruskal
出发点	从某一顶点扩张	从全局最小边开始
核心数据结构	优先队列	排序 + 并查集
时间复杂度	O((V+E) log V)	O(E log E)
适合图类型	稠密图	稀疏图

拓扑排序

拓扑排序：对有向无环图（DAG）的顶点进行线性排序，使每条边 (u→v) 中 u 都排在 v 之前。

典型应用：编译依赖、任务调度、课程先修关系、Makefile 构建顺序。

Kahn 算法（BFS + 入度）

public List<Integer> topoSort(int v, int[][] edges) {
    int[] inDegree = new int[v];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < v; i++) adj.add(new ArrayList<>());

    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        inDegree[e[1]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < v; i++)
        if (inDegree[i] == 0) queue.add(i); // 所有入度为 0 的顶点入队

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        result.add(u);
        for (int neighbor : adj.get(u)) {
            if (--inDegree[neighbor] == 0) // 入度归零，可以入队
                queue.add(neighbor);
        }
    }

    // 若结果不包含所有顶点，说明图中存在环（无法完成拓扑排序）
    if (result.size() < v) throw new RuntimeException("图中存在环，不是 DAG");
    return result;
}

为什么入度归零就能排？ 入度为 0 表示该任务已无任何前置依赖，可安全输出；输出它后删掉它的出边，让后继的入度降 1，新暴露出的无依赖任务继续输出。若最终输出数 < V，说明有环——环里的点入度永远降不到 0。

步骤：

1. 统计所有顶点的入度
2. 将入度为 0 的顶点加入队列
3. 出队一个顶点 u，将其所有邻居的入度减 1；若某邻居入度变为 0，入队
4. 重复直到队列为空

维度	值
时间复杂度	O(V+E)
空间复杂度	O(V)
检测环	result.size() < V 即有环

DFS 拓扑排序

DFS 完成后逆序输出即为拓扑序（后处理时间越大的顶点排越前），适合递归场景。

为什么后序逆序就是拓扑序？ DFS 在"某顶点的所有后继都处理完"后才把它入栈（后序）。于是栈中越靠后的顶点，其依赖越早处理完——逆序输出时，被依赖的顶点先于依赖它的顶点出现，正好满足"边 u→v 中 u 排在 v 前"。若 DFS 中遇到指向栈内未完成祖先的回边，说明存在环，不是 DAG。

public List<Integer> topoSortDFS(int v, List<List<Integer>> adj) {
    boolean[] visited = new boolean[v];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < v; i++)
        if (!visited[i]) dfsHelper(i, adj, visited, stack);
    List<Integer> result = new ArrayList<>(stack); // 栈顶 = 拓扑序第一个
    return result;
}

private void dfsHelper(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> stack) {
    visited[u] = true;
    for (int neighbor : adj.get(u))
        if (!visited[neighbor]) dfsHelper(neighbor, adj, visited, stack);
    stack.push(u); // 所有后继处理完后才入栈
}

图题解题决策框架

学完各个算法，真正做题时第一步不是写代码，而是判断这道题该用哪个算法。判断分三步走。

第一步：把题目抽象成图

绝大多数图题不会直接给你"图"的数据结构，而是披着场景外衣。先问自己两个问题：

问题	例子
什么当作顶点？	岛屿题里每个格子是顶点；课程表里每门课是顶点
什么当作边？	格子上下左右相邻有边；先修关系是一条有向边

抽象完，再确定三个属性：有向/无向、带权/无权、稀疏/稠密。这三个属性直接决定算法选择。

第二步：按问题类型选算法

题目问什么	关键词信号	选用算法	复杂度
两点间边数最少的路径 / 最少步数	"最少步数""最少操作""无权图"	BFS	O(V+E)
两点间权重最短的路径	"最短时间/距离""带权"	Dijkstra（无负权）/ Bellman-Ford（有负权）	O((V+E)logV) / O(VE)
任意两点最短路（n 小）	"所有点对""n≤100"	Floyd-Warshall	O(V³)
最少代价把所有点连成连通	"联网""连接所有点""最小代价"	MST：Prim 稠密 / Kruskal 稀疏	O(V²) / O(ElogE)
连通块个数 / 是否连通	"岛屿数""省份数""连通分量"	DFS/BFS 染色（静态）/ 并查集（动态加边）	O(V+E) / 近似 O(1)
任务先后顺序 / 能否完成	"依赖""先修""编译顺序"	拓扑排序	O(V+E)
删哪条边会断开	"关键连接""关键边"	Tarjan 求桥	O(V+E)
删哪个点会断开	"关键节点""割点"	Tarjan 求割点	O(V+E)
有向图互相可达的群体 / 环	"强连通""循环依赖"	Tarjan/Kosaraju 求 SCC	O(V+E)

第三步：决策流程

graph TD
    Q[看到一道图题] --> A{抽象成图<br/>确定: 有向? 带权? 稀疏?}
    A -->|无权 + 最少步数| BFS[BFS]
    A -->|带权 + 单源最短| D{有负权?}
    D -->|无| Di[Dijkstra]
    D -->|有| BF[Bellman-Ford]
    A -->|所有点对 + n小| F[Floyd-Warshall]
    A -->|连接所有点 + 最小代价| MST[MST: Prim/Kruskal]
    A -->|连通块或合并集合| C{边是否动态加入}
    C -->|静态| DFS2[DFS/BFS 染色]
    C -->|动态| UF[并查集]
    A -->|有向 + 依赖顺序| T[拓扑排序]
    A -->|无向 + 关键边或点| TB[Tarjan 桥/割点]
    A -->|有向 + 强连通或环| SCC[Tarjan 求 SCC]
    style BFS fill:#cfc,stroke:#060
    style Di fill:#cfc,stroke:#060
    style UF fill:#cfc,stroke:#060

常见陷阱信号

信号	含义	对策
二维网格 / 矩阵	隐式图，格子=点，上下左右=边	DFS/BFS 染色
"最少步数"且每步代价相同	等价于无权图最短	用 BFS，不是 DFS
有负权	Dijkstra 的贪心假设失效	改 Bellman-Ford 或 SPFA
n ≤ 100 且求"任意两点"	全源最短路规模小	Floyd O(n³)
链状图且 n=1e5	递归 DFS 栈深	改显式栈迭代
"能否到达"反复查询	多次连通性判断	并查集而非每次 DFS

核心心法：先抽象（点/边/方向/权），再看问的"量"是什么（最短/最小/连通/顺序/关键），最后匹配算法。同一问题常有多种解法，按约束（n 大小、有无负权、边静态动态）二次筛选。

参考资料

• 《数据结构与算法之美》— 第 30、31、43、44 章
• 图算法可视化（VisuAlgo）
• cp-algorithms：Finding bridges in a graph in O(N+M)