图算法

前置知识#

建议先阅读以下内容再进入本文：

• 算法分析基础与学习路线
• 搜索算法
• 离散数学

第 1 章 学习目标与导论#

1.1 本章在算法知识体系中的位置#

图（graph，源自希腊语 “graphos”，意为”书写、绘制”，由 James Joseph Sylvester 于 1878 年首次引入英语数学词汇，意为”由顶点与边绘制的关系结构”）是计算机科学中最重要、最具表达力的数据结构之一。它位于算法知识体系的”关系层”，向上承接搜索算法与动态规划，向下衔接网络流、字符串自动机与离散数学中的图论。

学习本章前，读者应当已经掌握：

• algorithm/算法分析基础与学习路线：渐近记号、最坏/平均复杂度分析
• algorithm/搜索算法：BFS/DFS 在树与状态空间上的基本框架
• math/离散数学：集合、关系、二元关系、等价关系与偏序关系

掌握本章后，读者将为后续学习 algorithm/网络流、algorithm/字符串算法（后缀自动机、AC 自动机的图结构）、algorithm/动态规划（DAG 上的 DP）等高级主题奠定坚实基础。

1.2 学习目标#

本章遵循 Bloom 分类法，按认知层级递进组织学习目标：

1. 记忆（Remember）：复述图的形式化定义 $G = (V, E)$ 与有向图、无向图、加权图、二分图的形式化区别。
2. 理解（Understand）：解释邻接矩阵与邻接表的代数表示，说明其在稠密图与稀疏图场景下的性能权衡。
3. 应用（Apply）：使用 BFS 与 DFS 实现连通分量、环检测、二分图判定与拓扑排序。
4. 分析（Analyze）：对比 Dijkstra、Bellman-Ford、Floyd-Warshall 算法的正确性证明（Loop Invariant 与最优子结构），识别其适用前提。
5. 评估（Evaluate）：评估 Kruskal 与 Prim 算法的 Cut 性质并选择适合稀疏图与稠密图的 MST 实现；评估 Tarjan 与 Kosaraju 的工程取舍。
6. 创造（Create）：设计基于图模型的工程方案，如社交网络分析、路由算法、依赖解析与推荐系统。

1.3 阅读建议#

• 零基础读者：先通读第 3、4、5 章，建立形式化定义与遍历直觉后回看第 2 章历史动机；
• 有数据结构基础读者：重点关注第 6、7、9 章的正确性证明与复杂度分析；
• 进阶读者：直接研读第 10、14 章的进阶算法与案例研究。

第 2 章 历史动机与演进#

2.1 1736：Euler 与哥尼斯堡七桥问题#

图论的诞生可追溯至 1736 年，瑞士数学家 Leonhard Euler（1707-1783）发表《Solutio problematis ad geometriam situs pertinentis》求解著名的”哥尼斯堡七桥问题”。普雷格尔河将哥尼斯堡（今俄罗斯加里宁格勒）分为两岸与两岛，其间由七座桥连接。市民们试图寻找一条路径，每座桥恰好走一次后回到起点。

Euler 的关键洞察是：桥的具体长度与地理位置无关，仅”哪两块陆地由几座桥连接”这一拓扑关系决定问题可解性。他将每块陆地抽象为顶点（vertex，源自拉丁语 “vertere”，意为”转动”，原指角的顶点，欧几里得几何中用于描述多边形的角点），每座桥抽象为边（edge，源自古英语 “ecg”，意为”刀刃、边界”），得到一个 4 顶点 7 边的多重图。

Euler 证明了：存在”每条边恰好经过一次的回路”（后称欧拉回路）当且仅当图中每个顶点的度数均为偶数。哥尼斯堡图所有顶点度数均为奇数，故无解。这一论证标志着图论与拓扑学的诞生，Euler 也因此被称为”图论之父”。

2.2 1857-1847：Cayley 与 Kirchhoff 的树与矩阵谱#

1857 年英国数学家 Arthur Cayley（1821-1895）在研究有机化学同分异构体计数时，系统化了”树”（tree）的概念，给出 Cayley 公式：$n$ 个标记顶点的不同树共有 $n^{n-2}$ 棵。这一结果奠定了组合图论的基础。

1847 年德国物理学家 Gustav Kirchhoff（1824-1887）在研究电路网络时提出了基尔霍夫矩阵树定理：图 $G$ 的生成树数量等于其 Laplacian 矩阵 $\mathbf{L}$ 任意余子式的值。这是图论与线性代数深度结合的里程碑，预示了后来谱图理论（spectral graph theory）的发展。

2.3 1936-1930s：Konig 与图论公理化#

匈牙利数学家 Denes Konig（1884-1944）于 1936 年出版《Theorie der endlichen und unendlichen Graphen》，这是第一部图论专著，标志着图论成为独立数学分支。Konig 系统化了图论的基本概念、定理与证明方法，并梳理了 Euler 至 1930s 的图论成果，包括 Kuratowski 平面图判定定理、Menger 定理、Hall 婚姻定理等。

同期 Paul Erdos（1913-1996）开创了极值图论与随机图论。他与 Alfred Renyi 于 1959 年提出 ER 随机图模型 $G(n, p)$，研究”几乎必然”性质与相变现象（如连通性阈值 $p = \ln n / n$）。这一工作深刻影响了 20 世纪后期的网络科学与复杂系统研究。

2.4 1956-1959：Kruskal、Prim 与 Dijkstra 的最优化算法#

第二次世界大战后，运筹学兴起推动了图优化算法的发展。

• 1956 年，Joseph Bernard Kruskal（1928-2010）在 Bell 实验室发表论文《On the shortest spanning subtree of a graph and the traveling salesman problem》，提出 Kruskal 最小生成树算法：按边权排序后逐步加入不形成环的边。其同事 Robert Clay Prim（1921-2021）于 1957 年提出改进算法（Prim 算法），从一个顶点出发逐步扩展。两者均基于 Cut 性质。

• 1959 年，荷兰数学家 Edsger Wybe Dijkstra（1930-2002）在 Numerische Mathematik 发表《A note on two problems in connexion with graphs》，提出最短路径算法。据 Dijkstra 本人在 2001 年的一次访谈中回忆，他在阿姆斯特丹的一家咖啡馆里花 20 分钟构思了该算法，目的是展示 ARMAC 计算机的能力。这一算法因其简洁高效而成为计算机科学中最广为引用的算法之一。

• 1958 年，Richard Bellman（1920-1984）发表 Bellman-Ford 算法（亦称 Bellman-Ford-Moore 算法），动态规划思想在图论中的典型应用，支持负权边与负环检测。

2.5 1962-1972：Floyd-Warshall 与 Tarjan 的线性算法#

1962 年 Robert Floyd（1936-2001）与 Stephen Warshall（1935-2007）分别独立提出全源最短路径算法（Floyd-Warshall），基于动态规划的中转点枚举。同年发表《Algorithm 97: Shortest path》。

1972 年 Robert Endre Tarjan（1948-）发表《Depth-first search and linear graph algorithms》，系统证明了 DFS 的线性时间复杂度，并基于此给出了强连通分量（SCC）、双连通分量、割点与桥的线性识别算法。Tarjan 的工作使”图论算法的复杂度从 $O(V^2)$ 进入 $O(V + E)$ 时代”，他因此获 1986 年图灵奖。同期 Sambasiva Rao Kosaraju（1947-）于 1978 年提出 Kosaraju SCC 算法，两次 DFS 完成识别。

2.6 1998：PageRank 与图论的现代复兴#

1998 年斯坦福大学博士生 Larry Page 与 Sergey Brin 提出 PageRank 算法（Page et al. 1999），将网页超链接结构建模为有向图，通过随机游走的平稳分布度量网页”重要性”。PageRank 成为 Google 搜索引擎的奠基技术，标志着图算法在大规模工业场景中的成功应用。

此后图算法在社交网络（朋友推荐、社区发现）、生物信息学（蛋白质相互作用网络）、推荐系统（知识图谱）、区块链（DAG 共识）等领域持续扩展。2000s 后图神经网络（GNN）的兴起进一步深化了图算法与机器学习的融合。

第 3 章 形式化定义与图论基础#

3.1 图的形式化定义#

为了消除自然语言的歧义，本节以数学形式化方式定义图的语义。该形式化对应 Bondy & Murty (2008) 与 CLRS 4th 第 20 章的约定。

定义 3.1（图）：图（graph）是一个有序三元组 $G = (V, E, \varphi)$，其中：

• $V$ 是有限非空集合，称为顶点集（vertex set），元素称为顶点（vertex）；
• $E$ 是有限集合，称为边集（edge set），元素称为边（edge）；
• $\varphi: E \to \mathcal{P}_2(V)$ 是关联函数，将每条边映射为顶点集的二元子集（无向图）或顶点的有序对（有向图）。

为简化记号，通常省略 $\varphi$，直接将边表示为 $e = (u, v)$。当 $V$ 与 $E$ 有限时，记 $|V| = n$、$|E| = m$。

定义 3.2（有向图与无向图）：

• 无向图（undirected graph）：$E \subseteq \binom{V}{2}$，边 $e = \{u, v\}$ 是无序对，表示 $u$ 与 $v$ 互为邻居。
• 有向图（directed graph / digraph）：$E \subseteq V \times V$，边 $e = (u, v)$ 是有序对，称为从 $u$ 指向 $v$ 的弧（arc），$u$ 为尾（tail）、$v$ 为头（head）。

定义 3.3（加权图）：加权图（weighted graph）是图 $G = (V, E)$ 配以权函数 $w: E \to \mathbb{R}$。对于无向图，$w(\{u, v\}) = w(\{v, u\})$；对于有向图，$w(u, v)$ 与 $w(v, u)$ 可不同。权可表示距离、代价、容量、概率等。

定义 3.4（二分图）：图 $G = (V, E)$ 称为二分图（bipartite graph），若存在 $V$ 的划分 $V = A \dot\cup B$，使得 $E \subseteq A \times B$（即所有边跨过 $A$、$B$ 两部分）。

定理 3.1（二分图判定）：图 $G$ 是二分图当且仅当 $G$ 不含奇环。

证明：$\Rightarrow$：若 $G$ 含奇环 $v_0 v_1 \dots v_{2k} v_0$，沿环交替着色，$v_0$ 与 $v_{2k}$ 同色但二者相邻，矛盾。$\Leftarrow$：对每个连通分量做 BFS，按层奇偶着色，无奇环保证相邻顶点不同色。

3.2 路径、回路与连通性#

定义 3.5（路径）：图 $G$ 中的路径（path）是顶点序列 $v_0, v_1, \dots, v_k$，使得对任意 $0 \leq i < k$，$(v_i, v_{i+1}) \in E$。路径长度为 $k$（边数），加权长度为 $\sum_{i=0}^{k-1} w(v_i, v_{i+1})$。

定义 3.6（简单路径与回路）：

• 简单路径（simple path）：所有顶点互不相同；
• 回路/环（cycle）：$v_0 = v_k$ 且 $k \geq 1$，且除首尾外顶点互不相同（简单环）；
• 欧拉路径/回路：经过每条边恰好一次的路径/回路；
• Hamilton 路径/回路：经过每个顶点恰好一次的路径/回路。

定义 3.7（连通性）：

• 无向图中 $u$ 与 $v$ 连通（connected），若存在 $u$ 到 $v$ 的路径。连通关系是 $V$ 上的等价关系，其等价类称为连通分量（connected component）。
• 有向图中 $u$ 可达 $v$（reachable），若存在 $u$ 到 $v$ 的有向路径。$u$ 与 $v$ 强连通（strongly connected），若互相可达。强连通关系是等价关系，其等价类称为强连通分量（strongly connected component, SCC）。

3.3 生成树与生成森林#

定义 3.8（生成树）：连通无向图 $G = (V, E)$ 的生成树（spanning tree，“spanning” 源自古英语 “spannan”，意为”伸展、跨越”，指覆盖所有顶点的树结构）是子图 $T = (V, E_T)$，其中 $E_T \subseteq E$、$|E_T| = |V| - 1$、$T$ 是树（无环连通）。

非连通图的对应概念为生成森林（spanning forest），每个连通分量各有一棵生成树。

定义 3.9（最小生成树）：加权图 $G = (V, E, w)$ 的最小生成树（minimum spanning tree, MST）$T^*$ 满足：

$T^* = \arg\min_{T \text{ 是 } G \text{ 的生成树}} \sum_{e \in T} w(e)$

定理 3.2（MST 唯一性）：若 $G$ 中所有边权互不相同，则 MST 唯一。

3.4 邻接矩阵与邻接表的代数表示#

定义 3.10（邻接矩阵）：图 $G = (V, E)$（$|V| = n$）的邻接矩阵 $\mathbf{A} \in \{0, 1\}^{n \times n}$（或 $\mathbb{R}^{n \times n}$ 用于加权图）定义为：

$\mathbf{A}_{ij} = \begin{cases} 1, & (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}$

加权图的邻接矩阵中 $\mathbf{A}_{ij} = w(v_i, v_j)$（无边时取 $\infty$ 或 $0$ 视约定）。

代数性质：

• 无向图的 $\mathbf{A}$ 对称：$\mathbf{A} = \mathbf{A}^\top$；
• $\mathbf{A}^k_{ij}$ 表示从 $v_i$ 到 $v_j$ 长度恰为 $k$ 的路径数；
• 度数矩阵 $\mathbf{D} = \text{diag}(\deg(v_1), \dots, \deg(v_n))$；
• Laplacian 矩阵 $\mathbf{L} = \mathbf{D} - \mathbf{A}$，其特征值与图的连通性、扩张性密切相关；
• 二分图的判定：$\mathbf{A}$ 经适当置换相似于 $\begin{pmatrix} 0 & \mathbf{B} \\ \mathbf{B}^\top & 0 \end{pmatrix}$。

定义 3.11（邻接表）：邻接表（adjacency list）将每个顶点 $v$ 映射到其邻居列表 $\text{Adj}(v) = \{u \mid (v, u) \in E\}$。形式上，邻接表是函数 $\text{Adj}: V \to \mathcal{P}(V)$。

存储复杂度对比：

第 4 章 图的表示方法与存储#

4.1 邻接矩阵实现#

# 邻接矩阵实现（Python）：稠密图场景
class GraphMatrix:
    """邻接矩阵表示的加权图

    适用于稠密图（E = Theta(V^2)）与频繁查询边存在的场景。
    空间复杂度 Theta(V^2)，查询边存在 O(1)，遍历邻居 O(V)。
    """
    def __init__(self, n: int, directed: bool = False):
        # n: 顶点数；directed: 是否有向
        self.n = n
        self.directed = directed
        # 初始化为 0 表示无边；权值非 0 表示有边
        self.adj = [[0] * n for _ in range(n)]

    def add_edge(self, u: int, v: int, w: int = 1) -> None:
        """添加边 (u, v)，权为 w"""
        self.adj[u][v] = w
        if not self.directed:
            self.adj[v][u] = w

    def has_edge(self, u: int, v: int) -> bool:
        """O(1) 查询边是否存在"""
        return self.adj[u][v] != 0

    def neighbors(self, u: int) -> list:
        """遍历 u 的所有邻居，O(V)"""
        return [v for v in range(self.n) if self.adj[u][v] != 0]

// 邻接矩阵实现（C++）：稠密图场景
#include <vector>
class GraphMatrix {
    int n;
    bool directed;
    std::vector<std::vector<int>> adj;
public:
    GraphMatrix(int n, bool dir = false)
        : n(n), directed(dir), adj(n, std::vector<int>(n, 0)) {}

    void addEdge(int u, int v, int w = 1) {
        adj[u][v] = w;
        if (!directed) adj[v][u] = w;
    }

    bool hasEdge(int u, int v) const {
        return adj[u][v] != 0;
    }

    int weight(int u, int v) const {
        return adj[u][v];
    }
};

4.2 邻接表实现#

# 邻接表实现（Python）：稀疏图场景
from collections import defaultdict

class GraphList:
    """邻接表表示的加权图

    适用于稀疏图（E = O(V)）与遍历为主的场景。
    空间复杂度 Theta(V + E)，查询边存在 O(deg(u))，遍历邻居 O(deg(u))。
    """
    def __init__(self, n: int, directed: bool = False):
        self.n = n
        self.directed = directed
        # 每个顶点维护 (邻居, 权值) 列表
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, w: int = 1) -> None:
        self.adj[u].append((v, w))
        if not self.directed:
            self.adj[v].append((u, w))

    def neighbors(self, u: int) -> list:
        """O(deg(u)) 遍历邻居"""
        return self.adj[u]

    def has_edge(self, u: int, v: int) -> bool:
        """O(deg(u)) 查询边存在"""
        return any(node == v for node, _ in self.adj[u])

// 邻接表实现（C++）：稀疏图场景
#include <vector>
#include <utility>
class GraphList {
    int n;
    bool directed;
    std::vector<std::vector<std::pair<int, int>>> adj;
public:
    GraphList(int n, bool dir = false) : n(n), directed(dir), adj(n) {}

    void addEdge(int u, int v, int w = 1) {
        adj[u].emplace_back(v, w);
        if (!directed) adj[v].emplace_back(u, w);
    }

    const std::vector<std::pair<int, int>>& neighbors(int u) const {
        return adj[u];
    }
};

// 邻接表实现（Java）：稀疏图场景
import java.util.*;

public class GraphList {
    private int n;
    private boolean directed;
    private List<List<int[]>> adj;

    public GraphList(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    }

    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new int[]{v, w});
        if (!directed) adj.get(v).add(new int[]{u, w});
    }

    public List<int[]> neighbors(int u) {
        return adj.get(u);
    }
}

4.3 链式前向星实现#

链式前向星是竞赛场景常用的紧凑表示，本质是用数组模拟邻接表的链表。

// 链式前向星实现（C++）：内存紧凑，竞赛常用
#include <cstring>
const int MAXN = 100010;
const int MAXM = 200010;

int head[MAXN];           // head[u] = u 的第一条边在 edges 数组中的下标
int nxt[MAXM];            // nxt[i] = 与 edges[i] 同起点的下一条边
int to[MAXM];             // edges[i] 的终点
int weight[MAXM];         // edges[i] 的权值
int edgeCnt = 0;          // 当前边数

void init() {
    std::memset(head, -1, sizeof(head));
    edgeCnt = 0;
}

void addEdge(int u, int v, int w) {
    to[edgeCnt] = v;
    weight[edgeCnt] = w;
    nxt[edgeCnt] = head[u];       // 新边指向原 head
    head[u] = edgeCnt++;          // 更新 head
}

// 遍历 u 的所有出边
void traverse(int u) {
    for (int e = head[u]; e != -1; e = nxt[e]) {
        int v = to[e];
        int w = weight[e];
        // 处理边 (u, v, w)
    }
}

4.4 表示方法选择#

4.5 图的输入与构建示例#

# 标准输入构建无向加权图
def build_undirected_graph():
    """从标准输入读取 n 个顶点、m 条边构建无向加权图

    输入格式：
    第一行：n m
    后续 m 行：u v w（顶点编号从 0 开始）
    """
    n, m = map(int, input().split())
    g = GraphList(n, directed=False)
    for _ in range(m):
        u, v, w = map(int, input().split())
        g.add_edge(u, v, w)
    return g

第 5 章 图的遍历：BFS 与 DFS#

5.1 广度优先搜索（BFS）#

广度优先搜索（Breadth-First Search, BFS，由 E. F. Moore (1959) 与 C. Y. Lee (1961) 独立提出，分别用于迷宫寻路与电路布线，名称反映其”逐层扩展”的搜索特征）按距离递增顺序访问顶点，是计算无权图最短路径的基础。

算法 5.1（BFS）：

from collections import deque

def bfs(n, graph, start):
    """广度优先搜索

    输入：顶点数 n、邻接表 graph、起始顶点 start
    输出：dist 数组（从 start 到各顶点的最短边数）、prev 数组（前驱）
    时间复杂度：O(V + E)
    """
    dist = [-1] * n
    prev = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _ in graph[u]:
            if dist[v] == -1:        # 未访问
                dist[v] = dist[u] + 1
                prev[v] = u
                q.append(v)
    return dist, prev

#include <queue>
#include <vector>
// BFS（C++ 实现）
std::vector<int> bfs(int n, std::vector<std::vector<std::pair<int,int>>>& graph, int start) {
    std::vector<int> dist(n, -1);
    std::vector<int> prev(n, -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& [v, w] : graph[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                prev[v] = u;
                q.push(v);
            }
        }
    }
    return dist;
}

5.2 BFS 正确性证明（Loop Invariant）#

定理 5.1（BFS 正确性）：BFS 结束时，dist[v] 等于从 start 到 v 的最短边数（无权最短路）。

证明（基于 Loop Invariant）：

Loop Invariant：在 BFS 主循环的每次迭代开始时，队列 q 中的顶点按 dist 非递减顺序排列，且对每个已访问顶点 $v$（dist[v] != -1），dist[v] 等于 start 到 $v$ 的最短边数 $\delta(s, v)$。

初始化：初始时 q = [start]、dist[start] = 0 = δ(s, s)，不变式成立。

保持：设当前弹出顶点为 $u$，其 dist[u] = d。对 $u$ 的每个未访问邻居 $v$，设 dist[v] = d + 1。需证 $\delta(s, v) = d + 1$：

• $\delta(s, v) \leq \delta(s, u) + 1 = d + 1$（$s \to u \to v$ 是一条长度 $d + 1$ 的路径）；
• 若 $\delta(s, v) < d + 1$，则存在长度 $\leq d$ 的路径 $s \to v$，但 $u$ 是当前队列中 dist 最小的未处理顶点（不变式保证队列非递减），故 $v$ 应已被某个 dist < d 的顶点松弛，与 $v$ 未访问矛盾。
• 故 $\delta(s, v) = d + 1$，不变式保持。

终止：所有顶点被处理后，dist[v] = δ(s, v) 对所有 $v$ 成立。

复杂度：每个顶点入队出队各一次（$O(V)$），每条边在无向图中被两端各遍历一次（$O(E)$），总计 $O(V + E)$。

5.3 深度优先搜索（DFS）#

深度优先搜索（Depth-First Search, DFS，由 Charles Pierre Tremaux (19th century) 在迷宫求解中提出，Tarjan (1972) 形式化并证明其线性时间复杂度，名称反映其”深入到底”的搜索特征）沿一条路径深入到底再回溯，是环检测、拓扑排序、SCC 的基础。

算法 5.2（DFS 递归实现）：

def dfs_recursive(n, graph, start):
    """DFS 递归实现

    输出：visited 数组、discovery/finish 时间戳
    时间复杂度：O(V + E)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    disc = [0] * n
    finish = [0] * n
    timer = [0]

    def dfs(u):
        timer[0] += 1
        disc[u] = timer[0]
        color[u] = GRAY
        for v, _ in graph[u]:
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        timer[0] += 1
        finish[u] = timer[0]

    dfs(start)
    return disc, finish

算法 5.3（DFS 迭代实现）：

def dfs_iterative(n, graph, start):
    """DFS 迭代实现，避免递归栈溢出

    注意：栈中需记录"下一个待访问邻居的下标"才能模拟递归回溯
    """
    visited = [False] * n
    order = []
    # 栈元素：(顶点, 下一个邻居下标)
    stack = [(start, 0)]
    visited[start] = True
    while stack:
        u, idx = stack[-1]
        if idx < len(graph[u]):
            stack[-1] = (u, idx + 1)
            v, _ = graph[u][idx]
            if not visited[v]:
                visited[v] = True
                stack.append((v, 0))
        else:
            stack.pop()
            order.append(u)
    return order

#include <vector>
#include <stack>
// DFS 迭代实现（C++）
std::vector<int> dfsIterative(int n, std::vector<std::vector<std::pair<int,int>>>& graph, int start) {
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    std::stack<std::pair<int, int>> stk;   // (顶点, 下一个邻居下标)
    stk.push({start, 0});
    visited[start] = true;
    while (!stk.empty()) {
        auto& [u, idx] = stk.top();
        if (idx < (int)graph[u].size()) {
            int v = graph[u][idx].first;
            idx++;
            if (!visited[v]) {
                visited[v] = true;
                stk.push({v, 0});
            }
        } else {
            stk.pop();
            order.push_back(u);
        }
    }
    return order;
}

5.4 DFS 边的分类#

DFS 遍历中，每条边 $(u, v)$ 根据发现时的顶点颜色分为四类：

定理 5.2（无向图 DFS 边分类）：无向图 DFS 中只存在树边与回边，无前向边与横叉边。

证明：考虑无向边 $(u, v)$，DFS 先到达其一（设为 $u$）。若 $v$ 未访问，则为树边；若 $v$ 已访问，因 $v$ 与 $u$ 邻接，$v$ 必在 $u$ 之前已被 DFS 完成或正在递归。若 $v$ 已完成（黑色），则 $u$ 必在 $v$ 的子树中（否则 $v$ 完成前会经 $(v, u)$ 访问 $u$），矛盾。故 $v$ 必为灰色，$(u, v)$ 为回边。

5.5 DFS 时间戳与括号化定理#

DFS 为每个顶点 $u$ 记录发现时间 $\text{disc}[u]$ 与完成时间 $\text{finish}[u]$。

定理 5.3（括号化定理）：对任意两顶点 $u, v$，区间 $[\text{disc}[u], \text{finish}[u]]$ 与 $[\text{disc}[v], \text{finish}[v]]$ 要么不相交，要么一个包含另一个；后者成立当且仅当一个是另一个的祖先。

推论 5.1（白色路径定理）：$v$ 是 $u$ 的后代当且仅当在发现 $u$ 时刻，存在从 $u$ 到 $v$ 的全白色顶点路径。

5.6 应用：连通分量、环检测、二分图判定#

def connected_components(n, graph):
    """计算无向图连通分量

    时间复杂度：O(V + E)
    """
    visited = [False] * n
    components = []
    for s in range(n):
        if not visited[s]:
            comp = []
            stack = [s]
            visited[s] = True
            while stack:
                u = stack.pop()
                comp.append(u)
                for v, _ in graph[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            components.append(comp)
    return components

def has_cycle_undirected(n, graph):
    """无向图环检测（DFS）"""
    visited = [False] * n
    def dfs(u, parent):
        visited[u] = True
        for v, _ in graph[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False
    for s in range(n):
        if not visited[s]:
            if dfs(s, -1):
                return True
    return False

def is_bipartite(n, graph):
    """二分图判定（BFS 染色法）

    返回 True 当且仅当图不含奇环
    """
    color = [-1] * n
    from collections import deque
    for s in range(n):
        if color[s] == -1:
            color[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v, _ in graph[u]:
                    if color[v] == -1:
                        color[v] = color[u] ^ 1
                        q.append(v)
                    elif color[v] == color[u]:
                        return False
    return True

5.7 BFS 与 DFS 可视化对比#

下图展示同一图在 BFS 与 DFS 下的访问顺序差异：

graph TB
    subgraph "原图"
        A1["A"] --- B1["B"]
        A1 --- C1["C"]
        B1 --- D1["D"]
        C1 --- D1
        C1 --- E1["E"]
        D1 --- E1
    end
    subgraph "BFS 访问顺序（A 出发）"
        A2["A<br/>dist=0"] --> B2["B<br/>dist=1"]
        A2 --> C2["C<br/>dist=1"]
        B2 --> D2["D<br/>dist=2"]
        C2 --> E2["E<br/>dist=2"]
    end
    subgraph "DFS 访问顺序（A 出发）"
        A3["A<br/>disc=1"] --> B3["B<br/>disc=2"]
        B3 --> D3["D<br/>disc=3"]
        D3 --> E3["E<br/>disc=4"]
        E3 -.-> C3["C<br/>disc=5"]
    end
    style A1 fill:#69f,color:#fff
    style A2 fill:#69f,color:#fff
    style A3 fill:#69f,color:#fff

第 6 章 最短路径算法#

6.1 问题定义#

单源最短路径（SSSP）问题：给定加权有向图 $G = (V, E, w)$ 与源点 $s \in V$，求 $s$ 到所有 $v \in V$ 的最短路径长度 $\delta(s, v) = \min_{p: s \to v} \sum_{e \in p} w(e)$。

全源最短路径（APSP）问题：对所有顶点对 $(u, v)$ 求 $\delta(u, v)$。

最优子结构：若 $s \to v$ 的最短路径为 $s \to u \to v$，则 $s \to u$ 也是最短路径。这是 Dijkstra 与 Bellman-Ford 共同的基础。

6.2 松弛操作#

所有最短路径算法的核心都是松弛（relaxation）操作：

$\text{Relax}(u, v, w): \quad \text{if } \text{dist}[u] + w(u, v) < \text{dist}[v] \text{ then } \text{dist}[v] \leftarrow \text{dist}[u] + w(u, v)$

def relax(dist, prev, u, v, w):
    """松弛边 (u, v, w)，返回是否成功松弛"""
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        prev[v] = u
        return True
    return False

收敛性质：若 $u$ 的最短路已确定（dist[u] = δ(s, u)），且 $(u, v) \in E$，则松弛 $(u, v)$ 后 dist[v] = δ(s, v)（或更早达到）。

6.3 Dijkstra 算法#

Dijkstra 算法基于贪心策略，要求所有边权非负。

算法 6.1（Dijkstra 朴素实现）：

def dijkstra_naive(n, graph, start):
    """Dijkstra 朴素实现（邻接矩阵）

    时间复杂度：O(V^2)
    适用：稠密图、V 较小
    """
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n
    visited = [False] * n
    dist[start] = 0
    for _ in range(n):
        # 选 dist 最小的未访问顶点
        u = -1
        for i in range(n):
            if not visited[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        if u == -1 or dist[u] == INF:
            break
        visited[u] = True
        for v, w in graph[u]:
            if not visited[v] and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    return dist, prev

算法 6.2（Dijkstra 堆优化）：

import heapq

def dijkstra_heap(n, graph, start):
    """Dijkstra 堆优化实现（邻接表 + 二叉堆）

    时间复杂度：O((V + E) log V)
    适用：稀疏图、大规模图
    关键：lazy deletion 模式跳过过期堆条目
    """
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n
    dist[start] = 0
    pq = [(0, start)]              # (距离, 顶点)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:            # lazy deletion：跳过过期条目
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, prev

#include <vector>
#include <queue>
#include <climits>
// Dijkstra 堆优化实现（C++）
std::vector<long long> dijkstra(int n, std::vector<std::vector<std::pair<int,int>>>& graph, int start) {
    const long long INF = LLONG_MAX / 4;
    std::vector<long long> dist(n, INF);
    std::vector<int> prev(n, -1);
    dist[start] = 0;
    // 优先队列：(距离, 顶点)，小根堆
    std::priority_queue<std::pair<long long,int>,
                        std::vector<std::pair<long long,int>>,
                        std::greater<>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;          // lazy deletion
        for (auto& [v, w] : graph[u]) {
            long long nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                prev[v] = u;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

// Dijkstra 堆优化实现（Java）
import java.util.*;

public class Dijkstra {
    public static long[] dijkstra(int n, List<List<int[]>> graph, int start) {
        final long INF = Long.MAX_VALUE / 4;
        long[] dist = new long[n];
        int[] prev = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[start] = 0;
        // 小根堆：(距离, 顶点)
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, start});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;       // lazy deletion
            for (int[] e : graph.get(u)) {
                int v = e[0], w = e[1];
                long nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    prev[v] = u;
                    pq.offer(new long[]{nd, v});
                }
            }
        }
        return dist;
    }
}

6.4 Dijkstra 正确性证明（贪心选择性质）#

定理 6.1（Dijkstra 贪心选择性质）：设所有边权非负，当顶点 $u$ 被从优先队列中取出时，dist[u] = δ(s, u)。

证明（反证法）：设 $u$ 是第一个被取出但 dist[u] > δ(s, u) 的顶点。设 $s \to u$ 的真实最短路径为 $s = v_0 \to v_1 \to \dots \to v_k = u$。沿该路径存在第一个”未访问”顶点 $v_i$（$v_0 = s$ 已访问），则 $v_{i-1}$ 已访问，dist[v_{i-1}] = δ(s, v_{i-1})（因 $u$ 是第一个违反性质的顶点）。

松弛 $(v_{i-1}, v_i)$ 后 dist[v_i] = δ(s, v_{i-1}) + w(v_{i-1}, v_i) = δ(s, v_i)。又因边权非负，$\delta(s, v_i) \leq \delta(s, u) < \text{dist}[u]$（最后一步用 $u$ 违反性质）。但 $v_i$ 在 $u$ 之前应被取出（dist[v_i] < dist[u]），与 $u$ 被先取出矛盾。

推论 6.1：Dijkstra 算法终止时，对所有 $v \in V$，dist[v] = δ(s, v)。

6.5 为何 Dijkstra 不能处理负权边#

# Dijkstra 负权失效反例
# 顶点：A=0, B=1, C=2
# 边：A->B(1), A->C(4), B->C(-3)
# 正确答案：dist[A]=0, dist[B]=1, dist[C]=-2
# Dijkstra 输出：dist[A]=0, dist[B]=1, dist[C]=4（错误）

graph = [[(1, 1), (2, 4)], [(2, -3)], []]
dist, _ = dijkstra_heap(3, graph, 0)
# dist = [0, 1, 4]，但正确答案是 [0, 1, -2]

失效机制：Dijkstra 取出 $C$ 时（dist[C] = 4）将其标记”已访问”，但 $B$ 到 $C$ 的负权边本可使 dist[C] = 1 + (-3) = -2 < 4。负权边破坏了”已访问顶点不会被后续松弛”的贪心选择性质。

6.6 Bellman-Ford 算法#

Bellman-Ford 通过对所有边执行 $V - 1$ 轮松弛，支持负权边与负环检测。

算法 6.3（Bellman-Ford）：

def bellman_ford(n, edges, start):
    """Bellman-Ford 算法

    输入：顶点数 n、边列表 [(u, v, w)]、源点 start
    输出：(dist 数组, 是否存在负环)
    时间复杂度：O(V * E)
    空间复杂度：O(V)
    """
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n
    dist[start] = 0
    # 第 k 轮松弛后，dist[v] = 至多经过 k 条边的最短路径长度
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                updated = True
        if not updated:             # 提前终止优化
            break
    # 第 V 轮：若仍能松弛，则存在负环
    has_neg_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_neg_cycle = True
            break
    return dist, has_neg_cycle

#include <vector>
#include <tuple>
// Bellman-Ford（C++）
std::pair<std::vector<long long>, bool> bellmanFord(
    int n, std::vector<std::tuple<int,int,int>>& edges, int start) {
    const long long INF = LLONG_MAX / 4;
    std::vector<long long> dist(n, INF);
    std::vector<int> prev(n, -1);
    dist[start] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                updated = true;
            }
        }
        if (!updated) break;
    }
    bool hasNegCycle = false;
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            hasNegCycle = true;
            break;
        }
    }
    return {dist, hasNegCycle};
}

6.7 Bellman-Ford 正确性证明#

定理 6.2（Bellman-Ford 正确性）：若图中无负环，则 $V - 1$ 轮松弛后 dist[v] = δ(s, v) 对所有从 $s$ 可达的 $v$ 成立。

证明（基于路径长度归纳）：

不变式：第 $k$ 轮松弛后，dist[v] 等于从 $s$ 到 $v$ 最多经过 $k$ 条边的最短路径长度。

归纳基础：$k = 0$ 时 dist[s] = 0、其余为 $\infty$，对应”0 条边路径”。

归纳步骤：设第 $k - 1$ 轮已得到所有”最多 $k - 1$ 条边”的最短路。对每条边 $(u, v)$ 松弛时，若 $u$ 的最短路已确定（至多 $k - 1$ 条边），则 dist[v] = min(dist[v], dist[u] + w(u, v)) 即为”至多 $k$ 条边”的最短路（最后一条边是 $(u, v)$）。

上界：无负环时，最短路径是简单路径（无重复顶点），最多 $V - 1$ 条边，故 $V - 1$ 轮足够。

负环检测：若第 $V$ 轮仍能松弛，则存在长度 $\geq V$ 的更短路径，必含重复顶点，即负环。

6.8 SPFA（队列优化 Bellman-Ford）#

SPFA（Shortest Path Faster Algorithm）只对发生松弛的顶点的出边进行松弛，平均性能优于 Bellman-Ford。

from collections import deque

def spfa(n, graph, start):
    """SPFA 算法（队列优化 Bellman-Ford）

    时间复杂度：平均 O(E)，最坏 O(V * E)
    负环检测：维护 cnt[v] = s 到 v 的最短路边数，cnt[v] >= V 时存在负环
    """
    INF = float('inf')
    dist = [INF] * n
    in_queue = [False] * n
    cnt = [0] * n              # 记录最短路边数
    dist[start] = 0
    in_queue[start] = True
    q = deque([start])
    has_neg_cycle = False
    while q and not has_neg_cycle:
        u = q.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                cnt[v] = cnt[u] + 1
                if cnt[v] >= n:                 # 边数 >= V，存在负环
                    has_neg_cycle = True
                    break
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
    return dist, has_neg_cycle

6.9 Floyd-Warshall 全源最短路径#

算法 6.4（Floyd-Warshall）：

DP 状态：$d^{(k)}[i][j]$ = 从 $i$ 到 $j$ 仅经过中间顶点 $\{0, 1, \dots, k-1\}$ 的最短路径长度。

转移方程：

$d^{(k)}[i][j] = \min\left( d^{(k-1)}[i][j],\ d^{(k-1)}[i][k] + d^{(k-1)}[k][j] \right)$

空间优化：因 $d^{(k)}$ 仅依赖 $d^{(k-1)}$，可用二维数组滚动，甚至原地更新（注意 $k$ 必须是最外层循环）。

def floyd_warshall(n, graph):
    """Floyd-Warshall 全源最短路径

    时间复杂度：O(V^3)
    空间复杂度：O(V^2)
    支持负权边，可检测负环（对角线 < 0）
    """
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u in range(n):
        for v, w in graph[u]:
            dist[u][v] = min(dist[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    # 负环检测：若 dist[i][i] < 0 则存在经过 i 的负环
    has_neg_cycle = any(dist[i][i] < 0 for i in range(n))
    return dist, has_neg_cycle

#include <vector>
// Floyd-Warshall（C++）
std::pair<std::vector<std::vector<long long>>, bool> floydWarshall(
    int n, std::vector<std::vector<std::pair<int,int>>>& graph) {
    const long long INF = LLONG_MAX / 4;
    std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int u = 0; u < n; u++) {
        for (auto& [v, w] : graph[u]) {
            dist[u][v] = std::min(dist[u][v], (long long)w);
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    bool hasNegCycle = false;
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) { hasNegCycle = true; break; }
    }
    return {dist, hasNegCycle};
}

6.10 Floyd-Warshall 正确性证明#

定理 6.3（Floyd-Warshall 正确性）：算法终止时 dist[i][j] = δ(i, j)（若无负环）。

证明（基于 $d^{(k)}$ 的归纳定义）：

归纳基础：$d^{(0)}[i][j] = w(i, j)$（直接边权，无边时为 $\infty$）。

归纳步骤：设 $d^{(k-1)}[i][j]$ 已正确表示”仅经过 $\{0, \dots, k-2\}$“的最短路。考虑 $d^{(k)}[i][j]$：

• 若 $i \to j$ 的最短路（限定中间顶点 $\subseteq \{0, \dots, k-1\}$）不经过 $k$，则 $d^{(k)}[i][j] = d^{(k-1)}[i][j]$。
• 若经过 $k$，则路径可分解为 $i \to k \to j$，两段均仅经过 $\{0, \dots, k-2\}$（因 $k$ 在两段之间只出现一次，否则可去除环路），故 $d^{(k)}[i][j] = d^{(k-1)}[i][k] + d^{(k-1)}[k][j]$。
• 取两者较小值，即转移方程。

终止：$k = V$ 时 $d^{(V)}[i][j]$ = 任意中间顶点的最短路 = 真实最短路。

6.11 最短路径算法对比#

6.12 A* 算法#

A* 是带启发式的最短路径算法，在路径搜索（地图导航、游戏 AI）中广泛应用。

评估函数：$f(n) = g(n) + h(n)$，其中 $g(n)$ 是从源点到 $n$ 的实际代价，$h(n)$ 是从 $n$ 到目标的启发式估计。

可采纳性：当 $h(n) \leq h^*(n)$（$h^*$ 是真实最短代价）时，A* 保证最优性。

import heapq

def astar(n, graph, start, goal, heuristic):
    """A* 算法

    输入：顶点数 n、邻接表 graph、起点 start、终点 goal、启发式函数 heuristic
    输出：(最短距离, 路径)
    要求：heuristic 必须可采纳（不高估真实代价）才能保证最优性
    """
    INF = float('inf')
    g = [INF] * n              # g[v] = start 到 v 的实际最短代价
    prev = [-1] * n
    g[start] = 0
    pq = [(heuristic(start), 0, start)]   # (f, g, 顶点)
    while pq:
        f, gu, u = heapq.heappop(pq)
        if u == goal:                       # 到达目标
            # 重建路径
            path = []
            v = goal
            while v != -1:
                path.append(v)
                v = prev[v]
            return gu, path[::-1]
        if gu > g[u]:                        # lazy deletion
            continue
        for v, w in graph[u]:
            gv = gu + w
            if gv < g[v]:
                g[v] = gv
                prev[v] = u
                heapq.heappush(pq, (gv + heuristic(v), gv, v))
    return INF, []

6.13 最短路径树可视化#

下图展示从源点 $s$ 出发的最短路径树（SPT）结构：

graph TB
    subgraph "原图"
        S0["s"] -->|10| A0["a"]
        S0 -->|5| B0["b"]
        A0 -->|1| C0["c"]
        B0 -->|3| A0
        B0 -->|9| C0
        B0 -->|2| D0["d"]
        D0 -->|6| C0
        D0 -->|7| E0["e"]
        C0 -->|4| E0
    end
    subgraph "最短路径树（s 出发）"
        S1["s<br/>d=0"] -->|5| B1["b<br/>d=5"]
        B1 -->|3| A1["a<br/>d=8"]
        B1 -->|2| D1["d<br/>d=7"]
        A1 -->|1| C1["c<br/>d=9"]
        D1 -->|7| E1["e<br/>d=14"]
    end
    style S0 fill:#6c6,color:#fff
    style S1 fill:#6c6,color:#fff

第 7 章 最小生成树#

7.1 Cut 性质#

定义 7.1（割）：图 $G = (V, E)$ 的割（cut）是顶点集的一个划分 $(S, V \setminus S)$，其中 $S \subseteq V$、$S \neq \emptyset$、$S \neq V$。横切该割的边集为 $\delta(S) = \{ (u, v) \in E \mid u \in S, v \notin S \}$。

定理 7.1（Cut 性质）：对任意割 $(S, V \setminus S)$，若横切边 $e$ 是 $\delta(S)$ 中权值最小的边，且所有横切边权值互不相同，则 $e$ 必属于 $G$ 的任意一棵 MST。

证明：设 $T$ 是一棵不含 $e$ 的 MST。则 $T \cup \{e\}$ 含环 $C$，$C$ 必含另一横切边 $e'$（环穿过割的次数为偶数）。因 $w(e) < w(e')$，用 $e$ 替换 $e'$ 得到 $T' = T - \{e'\} + \{e\}$，$w(T') < w(T)$，与 $T$ 是 MST 矛盾。

Cut 性质是 Kruskal 与 Prim 算法的共同基础。

7.2 Kruskal 算法#

Kruskal 算法按边权递增顺序逐步加入不形成环的边，依赖并查集高效判环。

算法 7.1（Kruskal）：

class UnionFind:
    """并查集（Union-Find）实现

    支持 path compression 与 union by rank 优化
    单次操作均摊复杂度 O(alpha(V))，其中 alpha 是反 Ackermann 函数
    """
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """合并 x、y 所在集合，返回是否成功（成功=True，已在同集合=False）"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """Kruskal 最小生成树算法

    输入：顶点数 n、边列表 [(u, v, w)]
    输出：(MST 总权值, MST 边列表)
    时间复杂度：O(E log E)，主导项为排序
    """
    edges_sorted = sorted(edges, key=lambda e: e[2])
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = []
    for u, v, w in edges_sorted:
        if uf.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break
    return mst_weight, mst_edges

#include <vector>
#include <algorithm>
// Kruskal（C++）
struct DSU {
    std::vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank_[px] < rank_[py]) std::swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        return true;
    }
};

long long kruskal(int n, std::vector<std::tuple<int,int,int>>& edges) {
    std::sort(edges.begin(), edges.end(),
              [](const auto& a, const auto& b) { return std::get<2>(a) < std::get<2>(b); });
    DSU dsu(n);
    long long total = 0;
    int cnt = 0;
    for (auto& [u, v, w] : edges) {
        if (dsu.unite(u, v)) {
            total += w;
            if (++cnt == n - 1) break;
        }
    }
    return total;
}

7.3 Kruskal 正确性证明#

定理 7.2（Kruskal 正确性）：Kruskal 算法终止时输出的边集构成一棵 MST。

证明（基于 Cut 性质归纳）：

设 Kruskal 依次加入边 $e_1, e_2, \dots, e_{n-1}$。维护不变式：第 $k$ 步后，已加入边集 $T_k = \{e_1, \dots, e_k\}$ 是某棵 MST 的子集。

基础：$T_0 = \emptyset$ 是任意 MST 的子集。

归纳：设 $T_{k-1}$ 是某 MST $T^*$ 的子集。考虑 $e_k = (u, v)$，加入时 $u, v$ 在 $T_{k-1}$ 中不连通。设 $S$ 为 $u$ 在 $T_{k-1}$ 中的连通分量，则 $e_k$ 横切割 $(S, V \setminus S)$。Kruskal 按 weight 递增选择，故 $e_k$ 是 $\delta(S)$ 中尚未被考虑的边里权值最小的。

需证 $e_k \in T^*$：若 $e_k \notin T^*$，由 Cut 性质（边权互异假设下），$T^*$ 中应含 $\delta(S)$ 的最小横切边 $e'$，且 $w(e') \leq w(e_k)$。但 $e'$ 必然在 $e_k$ 之前被 Kruskal 考虑过，且 $e'$ 加入时其两端不连通（否则 $T_{k-1}$ 中已有 $S$ 外的连通分量，矛盾），故 Kruskal 应已加入 $e'$ 而非 $e_k$，矛盾。

7.4 Prim 算法#

Prim 算法从一个顶点出发逐步扩展 MST，依赖优先队列维护跨切边。

算法 7.2（Prim 堆优化）：

import heapq

def prim(n, graph, start=0):
    """Prim 最小生成树算法（堆优化）

    输入：顶点数 n、邻接表 graph、起始顶点 start
    输出：(MST 总权值, MST 边列表)
    时间复杂度：O(E log V)
    """
    INF = float('inf')
    in_mst = [False] * n
    min_edge = [INF] * n          # min_edge[v] = 跨切集中到 v 的最小权
    min_edge[start] = 0
    prev = [-1] * n
    pq = [(0, start)]              # (权值, 顶点)
    mst_weight = 0
    mst_edges = []
    while pq:
        w, u = heapq.heappop(pq)
        if in_mst[u]:
            continue
        in_mst[u] = True
        mst_weight += w
        if prev[u] != -1:
            mst_edges.append((prev[u], u, w))
        for v, wuv in graph[u]:
            if not in_mst[v] and wuv < min_edge[v]:
                min_edge[v] = wuv
                prev[v] = u
                heapq.heappush(pq, (wuv, v))
    return mst_weight, mst_edges