第18章 最小生成树与拓扑排序

学习目标

• 掌握最小生成树的形式化定义与基本性质
• 理解切分定理与Kruskal、Prim算法的正确性证明
• 掌握并查集数据结构的实现与摊还分析
• 理解拓扑排序的理论基础与应用
• 掌握关键路径分析方法

---

18.1 最小生成树理论

18.1.1 基本定义

定义 18.1（生成树） 对于连通图 $G = (V, E)$，生成树 $T = (V, E_T)$ 是 $G$ 的子图，满足：

1. $T$ 是树（连通无环）
2. $E_T \subseteq E$
3. $|E_T| = |V| - 1$

定义 18.2（最小生成树） 对于带权连通图 $G = (V, E, w)$，最小生成树（MST）是权重最小的生成树：

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

定理 18.1（MST存在性） 连通图 $G$ 存在生成树当且仅当 $G$ 连通。

证明： （$\Rightarrow$）生成树是连通子图，故原图连通。

（$\Leftarrow$）若 $G$ 无环，则 $G$ 本身是树。若 $G$ 有环，删除环上任一边仍保持连通。重复此过程直到无环，得到生成树。 ∎

18.1.2 切分定理

定义 18.3（切分） 图 $G = (V, E)$ 的切分是将 $V$ 划分为两个非空子集 $S$ 和 $V \setminus S$。

定义 18.4（横跨边） 对于切分 $(S, V \setminus S)$，横跨边是连接 $S$ 与 $V \setminus S$ 的边：

$$E_{\text{cross}} = {(u, v) \in E : u \in S, v \notin S}$$

定理 18.2（切分定理） 对于图 $G$ 的任意切分，设 $e$ 是横跨边中权重最小的边。则存在 $G$ 的最小生成树包含 $e$。

证明：设 $T^$ 是 $G$ 的MST。若 $e \in T^$，结论成立。

若 $e \notin T^$，将 $e$ 加入 $T^$ 形成环 $C$。由于 $e$ 是横跨边，$C$ 中必有另一横跨边 $e'$。

由 $e$ 的最小性，$w(e) \leq w(e')$。用 $e$ 替换 $e'$ 得到 $T' = T^* - e' + e$：

$$w(T') = w(T^) - w(e') + w(e) \leq w(T^)$$

由于 $T^$ 是MST，$w(T') = w(T^)$，故 $T'$ 也是MST且包含 $e$。 ∎

推论 18.1 切分定理是贪心算法正确性的基础：每次选择横跨最小切分的最小边。

18.1.3 MST的唯一性

定理 18.3 若图中所有边权重互不相同，则MST唯一。

证明：反证法。设存在两个不同的MST $T_1$ 和 $T_2$。设 $e$ 是 $T_1$ 中最小权重的边且 $e \notin T_2$。

将 $e$ 加入 $T_2$ 形成环 $C$。$C$ 中必有边 $e' \in T_2$ 且 $e' \notin T_1$（否则 $T_1$ 有环）。

由 $e$ 的选择，$w(e) < w(e')$。用 $e$ 替换 $e'$ 得到更小的生成树，矛盾。 ∎

---

18.2 Kruskal算法

18.2.1 算法描述

算法 18.1（Kruskal）

Kruskal(G, w):
    A = ∅
    for each vertex v ∈ G.V:
        Make-Set(v)
    sort edges by weight
    for each edge (u, v) ∈ G.E in sorted order:
        if Find-Set(u) ≠ Find-Set(v):
            A = A ∪ {(u, v)}
            Union(u, v)
    return A

18.2.2 正确性证明

定理 18.4（Kruskal正确性） Kruskal算法返回最小生成树。

证明：使用循环不变式：在每次迭代前，$A$ 是某MST的子集。

初始化：$A = \emptyset$，显然是MST的子集。

保持：设 $(u, v)$ 是当前考虑的边，$A$ 是某MST $T^*$ 的子集。若 $u, v$ 在同一连通分量，加入 $(u, v)$ 会形成环，跳过。

若 $u, v$ 在不同连通分量，设 $S$ 为 $u$ 所在连通分量的顶点集。$(u, v)$ 是切分 $(S, V \setminus S)$ 的横跨边，且是所有横跨边中权重最小的（因为边按权重排序，之前的横跨边已被处理）。

由切分定理，存在包含 $(u, v)$ 的MST。故 $A \cup {(u, v)}$ 是某MST的子集。

终止：当算法终止时，$A$ 有 $|V| - 1$ 条边且无环，故是生成树。由不变式，$A$ 是MST的子集，故 $A$ 是MST。 ∎

18.2.3 复杂度分析

定理 18.5 使用路径压缩和按秩合并的并查集，Kruskal算法时间复杂度为 $O(|E| \log |E|) = O(|E| \log |V|)$。

证明：

• 排序：$O(|E| \log |E|) = O(|E| \log |V|)$
• 并查集操作：$O(|E| \cdot \alpha(|V|))$，其中 $\alpha$ 是反阿克曼函数

排序主导复杂度。 ∎

18.2.4 Python实现

from typing import List, Tuple, Dict, Set, Generic, TypeVar, Optional
from dataclasses import dataclass

V = TypeVar('V')
W = TypeVar('W', int, float)

@dataclass
class Edge(Generic[V, W]):
    u: V
    v: V
    weight: W
    
    def __lt__(self, other):
        return self.weight < other.weight

class UnionFind(Generic[V]):
    def __init__(self):
        self._parent: Dict[V, V] = {}
        self._rank: Dict[V, int] = {}
        self._size: int = 0
    
    def make_set(self, x: V) -> None:
        if x not in self._parent:
            self._parent[x] = x
            self._rank[x] = 0
            self._size += 1
    
    def find(self, x: V) -> V:
        if x not in self._parent:
            self.make_set(x)
        
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]
    
    def union(self, x: V, y: V) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        
        if root_x == root_y:
            return False
        
        if self._rank[root_x] < self._rank[root_y]:
            root_x, root_y = root_y, root_x
        
        self._parent[root_y] = root_x
        
        if self._rank[root_x] == self._rank[root_y]:
            self._rank[root_x] += 1
        
        self._size -= 1
        return True
    
    def connected(self, x: V, y: V) -> bool:
        return self.find(x) == self.find(y)
    
    def count(self) -> int:
        return self._size

def kruskal(vertices: Set[V], edges: List[Edge[V, W]]) -> Tuple[List[Edge[V, W]], W]:
    sorted_edges = sorted(edges, key=lambda e: e.weight)
    
    uf = UnionFind[V]()
    for v in vertices:
        uf.make_set(v)
    
    mst: List[Edge[V, W]] = []
    total_weight = 0
    
    for edge in sorted_edges:
        if uf.union(edge.u, edge.v):
            mst.append(edge)
            total_weight += edge.weight
            
            if len(mst) == len(vertices) - 1:
                break
    
    return mst, total_weight

def kruskal_graph(g: WeightedGraph[V, W]) -> Tuple[List[Edge[V, W]], W]:
    vertices = g.vertices()
    edges = [Edge(e.source, e.target, e.weight) for e in g.edges_with_weights()]
    return kruskal(vertices, edges)

class KruskalMST(Generic[V, W]):
    def __init__(self, g: WeightedGraph[V, W]):
        self._graph = g
        self._mst: Optional[List[Edge[V, W]]] = None
        self._weight: Optional[W] = None
    
    def compute(self) -> Tuple[List[Edge[V, W]], W]:
        if self._mst is None:
            self._mst, self._weight = kruskal_graph(self._graph)
        return self._mst, self._weight
    
    def edges(self) -> List[Edge[V, W]]:
        mst, _ = self.compute()
        return mst
    
    def weight(self) -> W:
        _, weight = self.compute()
        return weight

---

18.3 Prim算法

18.3.1 算法描述

算法 18.2（Prim）

Prim(G, w, r):
    for each u ∈ G.V:
        u.key = ∞
        u.π = NIL
    r.key = 0
    Q = G.V
    while Q ≠ ∅:
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]:
            if v ∈ Q and w(u, v) < v.key:
                v.key = w(u, v)
                v.π = u

18.3.2 正确性证明

定理 18.6（Prim正确性） Prim算法返回最小生成树。

证明：使用循环不变式：在每次迭代前，$A = {(v, v.\pi) : v \in V - Q, v \neq r}$ 是某MST的子集。

初始化：$A = \emptyset$，是MST的子集。

保持：设 $u$ 被加入 $A$。考虑切分 $(S, V \setminus S)$，其中 $S$ 是已加入的顶点集。

$u.key$ 是连接 $u$ 到 $S$ 的最小边权重。由切分定理，存在包含此边的MST。

终止：$Q = \emptyset$，所有顶点已加入，$A$ 是生成树且是MST的子集，故 $A$ 是MST。 ∎

18.3.3 复杂度分析

定理 18.7 使用二叉堆的Prim算法时间复杂度为 $O(|E| \log |V|)$。

证明：

• Extract-Min：$|V|$ 次，每次 $O(\log |V|)$
• Decrease-Key：最多 $|E|$ 次，每次 $O(\log |V|)$

总计 $O((|V| + |E|) \log |V|) = O(|E| \log |V|)$。 ∎

定理 18.8 使用斐波那契堆的Prim算法时间复杂度为 $O(|E| + |V| \log |V|)$。

18.3.4 Python实现

import heapq
from typing import Dict, List, Tuple, Set, Optional, Generic, TypeVar
import math

V = TypeVar('V')
W = TypeVar('W', int, float)

def prim(g: WeightedGraph[V, W], start: Optional[V] = None) -> Tuple[List[Edge[V, W]], W]:
    vertices = list(g.vertices())
    if not vertices:
        return [], 0
    
    if start is None:
        start = vertices[0]
    
    in_mst: Set[V] = set()
    mst: List[Edge[V, W]] = []
    total_weight = 0
    
    pq: List[Tuple[W, V, Optional[V]]] = [(0, start, None)]
    
    while pq and len(in_mst) < len(vertices):
        weight, u, parent = heapq.heappop(pq)
        
        if u in in_mst:
            continue
        
        in_mst.add(u)
        
        if parent is not None:
            mst.append(Edge(parent, u, weight))
            total_weight += weight
        
        for v in g.neighbors(u):
            if v not in in_mst:
                edge_weight = g.get_weight(u, v)
                if edge_weight is not None:
                    heapq.heappush(pq, (edge_weight, v, u))
    
    return mst, total_weight

class PrimMST(Generic[V, W]):
    def __init__(self, g: WeightedGraph[V, W]):
        self._graph = g
        self._mst: Optional[List[Edge[V, W]]] = None
        self._weight: Optional[W] = None
    
    def compute(self, start: Optional[V] = None) -> Tuple[List[Edge[V, W]], W]:
        if self._mst is None:
            self._mst, self._weight = prim(self._graph, start)
        return self._mst, self._weight
    
    def edges(self) -> List[Edge[V, W]]:
        mst, _ = self.compute()
        return mst
    
    def weight(self) -> W:
        _, weight = self.compute()
        return weight

---

18.4 并查集深入分析

18.4.1 操作定义

定义 18.5（并查集操作）

• $\text{Make-Set}(x)$：创建单元素集合 ${x}$
• $\text{Find}(x)$：返回包含 $x$ 的集合代表
• $\text{Union}(x, y)$：合并包含 $x$ 和 $y$ 的集合

18.4.2 路径压缩

定义 18.6（路径压缩） 在 $\text{Find}(x)$ 操作中，将路径上所有节点的父指针直接指向根。

定理 18.9 路径压缩不改变集合结构，但加速后续操作。

18.4.3 按秩合并

定义 18.7（秩） 节点的秩是其到叶子的最长路径高度。

定义 18.8（按秩合并） 合并时，将秩较小的树连接到秩较大的树。

定理 18.10 使用按秩合并，树的高度为 $O(\log n)$。

证明：对树的大小归纳。单节点树高度为 $0$。合并两棵树时，若秩不同，新树高度不变；若秩相同，新树高度增加 $1$。只有当两棵大小至少为 $2^r$ 的树合并时，秩才增加到 $r+1$。故秩为 $r$ 的树至少有 $2^r$ 个节点。 ∎

18.4.4 摊还分析

定义 18.9（阿克曼函数）

$$A(i, j) = \begin{cases} 2^j & i = 0 \ A(i-1, 1) & i > 0, j = 0 \ A(i-1, A(i, j-1)) & i > 0, j > 0 \end{cases}$$

定义 18.10（反阿克曼函数）

$$\alpha(n) = \min{i : A(i, 1) \geq n}$$

定理 18.11（Tarjan定理） 使用路径压缩和按秩合并，$m$ 次操作的总时间为 $O(m \cdot \alpha(n))$。

证明概要：定义势能函数，使用聚合分析。路径压缩使得后续Find操作更快，摊还代价接近常数。$\alpha(n)$ 增长极慢，对于所有实际输入 $\alpha(n) \leq 4$。 ∎

class OptimizedUnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
        self._count = n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def find_iterative(self, x: int) -> int:
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        
        while self.parent[x] != root:
            next_node = self.parent[x]
            self.parent[x] = root
            x = next_node
        
        return root
    
    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        
        if px == py:
            return False
        
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        self.size[px] += self.size[py]
        
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        self._count -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    
    def component_size(self, x: int) -> int:
        return self.size[self.find(x)]
    
    def count(self) -> int:
        return self._count

---

18.5 拓扑排序

18.5.1 基本定义

定义 18.11（拓扑排序） 有向无环图（DAG）的拓扑排序是将顶点排成线性序列，使得对于每条有向边 $(u, v)$，$u$ 在序列中位于 $v$ 之前。

定理 18.12 有向图存在拓扑排序当且仅当图是DAG。

证明： （$\Rightarrow$）若存在拓扑排序，则边都从前向后，不可能有环。

（$\Leftarrow$）若图是DAG，必存在入度为 $0$ 的顶点（否则所有顶点都有入边，可沿边无限行走，必遇环）。删除该顶点后仍是DAG，归纳构造拓扑排序。 ∎

18.5.2 Kahn算法

算法 18.3（Kahn）

Kahn(G):
    for each vertex v ∈ G.V:
        compute in-degree[v]
    Q = {v : in-degree[v] = 0}
    result = []
    while Q ≠ ∅:
        u = dequeue(Q)
        result.append(u)
        for each v ∈ G.Adj[u]:
            in-degree[v] -= 1
            if in-degree[v] == 0:
                enqueue(Q, v)
    if |result| = |G.V|:
        return result
    else:
        return "Graph has a cycle"

定理 18.13（Kahn正确性） Kahn算法返回拓扑排序当且仅当图是DAG。

证明：

• 若返回完整序列：每次出队的顶点入度为 $0$，删除后不影响已排序顶点的约束关系。
• 若无法完成：存在环，环上顶点入度永不为 $0$。 ∎

18.5.3 DFS算法

定理 18.14 按完成时间递减顺序排列DFS访问的顶点，得到拓扑排序。

证明：对于边 $(u, v)$，在DFS中：

• 若 $u$ 先被发现，则 $v$ 在 $u$ 完成前完成
• 若 $v$ 先被发现，则 $v$ 完成后 $u$ 才被发现

无论哪种情况，$u$ 的完成时间都大于 $v$，故按完成时间递减排列满足拓扑序。 ∎

18.5.4 Python实现

from collections import deque
from typing import Dict, List, Set, Optional, Generic, TypeVar

V = TypeVar('V')

def kahn_topological_sort(g: Graph[V]) -> Optional[List[V]]:
    in_degree: Dict[V, int] = {v: 0 for v in g.vertices()}
    
    for u in g.vertices():
        for v in g.neighbors(u):
            in_degree[v] = in_degree.get(v, 0) + 1
    
    queue = deque([v for v in g.vertices() if in_degree[v] == 0])
    result: List[V] = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        for v in g.neighbors(u):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) == g.vertex_count():
        return result
    return None

def dfs_topological_sort(g: Graph[V]) -> Optional[List[V]]:
    color: Dict[V, str] = {v: 'white' for v in g.vertices()}
    result: List[V] = []
    has_cycle = [False]
    
    def dfs(u: V) -> None:
        if has_cycle[0]:
            return
        
        color[u] = 'gray'
        
        for v in g.neighbors(u):
            if color[v] == 'white':
                dfs(v)
            elif color[v] == 'gray':
                has_cycle[0] = True
                return
        
        color[u] = 'black'
        result.append(u)
    
    for v in g.vertices():
        if color[v] == 'white':
            dfs(v)
    
    if has_cycle[0]:
        return None
    
    return result[::-1]

class TopologicalSort(Generic[V]):
    def __init__(self, g: Graph[V]):
        self._graph = g
        self._order: Optional[List[V]] = None
    
    def sort(self) -> Optional[List[V]]:
        if self._order is None:
            self._order = kahn_topological_sort(self._graph)
        return self._order
    
    def is_dag(self) -> bool:
        return self.sort() is not None
    
    def has_cycle(self) -> bool:
        return self.sort() is None

---

18.6 关键路径分析

18.6.1 AOE网

定义 18.12（AOE网） 活动在边上的网络（Activity On Edge）是用边表示活动、顶点表示事件的有向无环图。

定义 18.13（关键路径） 从源点到汇点的最长路径，决定了工程的最短完成时间。

18.6.2 时间计算

定义 18.14（事件时间）

• 最早发生时间：$v_e(v) = \max{v_e(u) + w(u, v) : (u, v) \in E}$
• 最迟发生时间：$v_l(v) = \min{v_l(w) - w(v, w) : (v, w) \in E}$

定义 18.15（活动时间）

• 最早开始时间：$e(a) = v_e(u)$，其中 $a = (u, v)$
• 最迟开始时间：$l(a) = v_l(v) - w(a)$

定义 18.16（关键活动） 松弛时间为 $0$ 的活动：$l(a) - e(a) = 0$。

from typing import Dict, List, Tuple, Optional
import math

def critical_path(g: WeightedGraph[V, float]) -> Tuple[Optional[List[V]], float]:
    order = kahn_topological_sort(g)
    if order is None:
        return None, 0
    
    vertices = list(g.vertices())
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    
    ve: Dict[V, float] = {v: 0 for v in vertices}
    for u in order:
        for v in g.neighbors(u):
            w = g.get_weight(u, v)
            if w is not None:
                ve[v] = max(ve[v], ve[u] + w)
    
    vl: Dict[V, float] = {v: math.inf for v in vertices}
    sink = order[-1]
    vl[sink] = ve[sink]
    
    for u in reversed(order):
        for v in g.neighbors(u):
            w = g.get_weight(u, v)
            if w is not None:
                vl[u] = min(vl[u], vl[v] - w)
    
    critical_edges: List[Tuple[V, V]] = []
    for u in vertices:
        for v in g.neighbors(u):
            w = g.get_weight(u, v)
            if w is not None:
                e = ve[u]
                l = vl[v] - w
                if abs(l - e) < 1e-9:
                    critical_edges.append((u, v))
    
    return critical_edges, ve[sink]

class CriticalPathAnalysis(Generic[V]):
    def __init__(self, g: WeightedGraph[V, float]):
        self._graph = g
        self._critical_edges: Optional[List[Tuple[V, V]]] = None
        self._duration: Optional[float] = None
    
    def analyze(self) -> Tuple[List[Tuple[V, V]], float]:
        if self._critical_edges is None:
            self._critical_edges, self._duration = critical_path(self._graph)
        return self._critical_edges, self._duration
    
    def get_critical_edges(self) -> List[Tuple[V, V]]:
        edges, _ = self.analyze()
        return edges
    
    def get_duration(self) -> float:
        _, duration = self.analyze()
        return duration

---

18.7 算法比较

18.7.1 MST算法比较

算法	时间复杂度	适用场景
Kruskal	$O(E \log E)$	稀疏图，边已排序
Prim（二叉堆）	$O(E \log V)$	一般图
Prim（斐波那契堆）	$O(E + V \log V)$	稠密图
Borůvka	$O(E \log V)$	并行计算

18.7.2 拓扑排序比较

算法	时间复杂度	特点
Kahn	$O(V + E)$	可检测环
DFS	$O(V + E)$	同时计算时间戳

---

18.8 本章小结

本章系统介绍了MST和拓扑排序：

1. 切分定理：MST贪心算法的理论基础
2. Kruskal算法：基于并查集，$O(E \log E)$
3. Prim算法：基于优先队列，$O(E \log V)$
4. 并查集：路径压缩与按秩合并，摊还 $O(\alpha(n))$
5. 拓扑排序：Kahn与DFS方法，$O(V + E)$
6. 关键路径：工程调度的理论基础

---

参考文献

1. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.
2. Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389-1401.
3. Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215-225.
4. Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM, 5(11), 558-562.
5. Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.

---

下一章：第19章 排序算法概述