假设你是一家电信公司的工程师负责在若干城市之间铺设光缆。任意两座城市之间铺设光缆的成本已知你的目标是用最小的总成本将所有城市连通。这个问题抽象为图论语言就是给定连通无向图 G(V,E)G(V,E)每条边有权重 w(u,v)w(u,v)找出一个连通所有顶点的无环子图即一棵生成树且边权总和最小。这就是最小生成树问题。最小生成树是贪心算法成功应用的典型案例。但贪心为何在这个问题上总是对的答案藏在一条看似平凡却内涵深刻的定理之中。一、安全边定理贪心选择的正确性基石将最小生成树问题的贪心策略统一在一个理论框架下是理解所有生成树算法的关键。这个框架的核心是安全边定理。设无向连通图 G(V,E)G(V,E)权重函数为 ww。设 AA 是某棵最小生成树的边子集初始可为空。若存在 GG 的一个割 (S,V−S)(S,V−S)使得割尊重 AA即 AA 中没有边跨越该割边 (u,v)(u,v) 是跨越该割的所有边中权重最小的一条即轻量级边则 (u,v)(u,v) 对于 AA 是安全的——将其加入 AA 后AA 仍然是某棵最小生成树的子集。这条定理的证明并不复杂。设 TT 是包含 AA 的一棵最小生成树。若 (u,v)∈T(u,v)∈T则命题成立。若 (u,v)∉T(u,v)∈/T由于 TT 连通TT 中必存在路径连接 uu 和 vv该路径上必有一条边 (x,y)(x,y) 跨越割 (S,V−S)(S,V−S)。将 (u,v)(u,v) 加入 TT 会形成环删除 (x,y)(x,y) 则打破环并恢复树结构。由轻量级边的定义知 w(u,v)≤w(x,y)w(u,v)≤w(x,y)新树的权重不大于 TT故仍为最小生成树且包含 A∪{(u,v)}A∪{(u,v)}。证毕。安全边定理不仅给出了贪心策略的理论保证更揭示了两种经典的算法设计路径Prim算法每次维护一个不断增长的顶点集合 SS在连接 SS 与 V−SV−S 的割中选最小边Kruskal算法则按全局边权排序每次选一条不会形成环的最小边——这两者均满足安全边定理的条件只是割的选择方式不同。二、Prim算法围绕顶点集的生长策略Prim算法将生成树从一个根顶点开始逐步“生长”。初始时 S{r}S{r}A∅A∅。每一步在连接 SS 与 V−SV−S 的所有边中选一条权重最小的将其加入 AA并将该边在 V−SV−S 中的端点加入 SS。重复直到 SVSV。高效的实现依赖最小优先队列。对每个顶点 v∈V−Sv∈V−S维护一个键值 key[v]key[v]表示当前连接 vv 与 SS 中任意顶点的最小边权。每轮从优先队列中取出键值最小的顶点 uu将其加入 SS然后检查 uu 的所有邻边 (u,v)(u,v)若 v∈V−Sv∈V−S 且 w(u,v)key[v]w(u,v)key[v]则更新 key[v]key[v] 并调整优先队列。若优先队列以二叉堆实现则每次取最小键值操作为 O(logn)O(logn)每条边至多触发一次键值更新也是 O(logn)O(logn)总复杂度为 O(mlogn)O(mlogn)。若采用斐波那契堆键值更新的平摊代价降至 O(1)O(1)总复杂度可优化至 O(mnlogn)O(mnlogn)。不过在工程实践中二叉堆版本因其常数因子小且实现简单仍是主流选择。三、Kruskal算法全局贪心的边排序策略Kruskal算法采取截然不同的视角它不再专注于某个不断扩张的连通区域而是将全部边按权重从小到大排序依次检查每条边——若当前边连接两个不同的连通分量则将其加入生成树否则舍弃。当生成树包含 n−1n−1 条边时算法终止。判断一条边是否连接不同连通分量的数据结构是并查集。初始时每个顶点自成一集合。检查边 (u,v)(u,v) 时调用 Find(u)Find(u) 与 Find(v)Find(v) 判断二者是否同属一个集合若不同则执行 Union(u,v)Union(u,v) 合并两个集合并将该边加入 AA。采用按秩合并和路径压缩两项优化后并查集的单次操作平摊代价几乎为常数准确界为 O(α(n))O(α(n))其中 αα 为反阿克曼函数在实践中可视为不超过4的常数。Kruskal算法的时间复杂度的主导项在于边排序——O(mlogm)O(mlogm)。并查集的操作总代价仅为 O(m⋅α(n))O(m⋅α(n))。由于 mO(n2)mO(n2) 且 logmO(logn)logmO(logn)整体复杂度可写为 O(mlogn)O(mlogn)。四、稀疏图与稠密图的适用性抉择Prim算法和Kruskal算法的渐进复杂度相同——均为 O(mlogn)O(mlogn)在二叉堆实现下。但常数因子和实际表现因图的稠密程度而异。对于稀疏图mΘ(n)mΘ(n)Kruskal算法往往更优。排序的 O(mlogm)O(mlogm) 实际开销有限且并查集的操作极其轻量。Prim算法则需要维护优先队列堆操作的常数因子相对较大。对于稠密图mΘ(n2)mΘ(n2)Prim算法的简单版本甚至可以不用堆仅维护一个数组记录每个顶点到当前 SS 的最小边权每轮暴力扫描所有顶点找到最小值总复杂度 O(n2)O(n2)。当 m≈n2m≈n2 时O(n2)O(n2) 优于 O(mlogn)O(mlogn)。因此稠密图场景下Prim的朴素实现反而是实用的选择。此外Kruskal算法的优势在于它天然适合处理边集不完整给出的情形——只要边按权重的排序流式可用算法便可逐步推进。Prim算法则要求图在内存中以邻接结构存储更适合随机访问顶点邻边的场景。五、理论延伸与应用最小生成树不仅是网络设计的基础工具也在更广泛的算法领域扮演支撑角色。在近似算法中旅行商问题的Christofides算法以最小生成树为起点构造近似解达到了3/2的近似比。在聚类分析中对数据集构建以距离为权重的完全图其最小生成树的最长边决定了单链接聚类的合并阈值。从安全边定理出发Prim与Kruskal殊途同归。贪心策略之所以在这里成功本质上是因为最小生成树问题构成一个拟阵——我们在第8篇中论证过带权拟阵上的贪心算法必然得到最优解。这个视角的统一性正是理论计算机科学最令人着迷之处。下一篇我们将从生成树转向路径问题探讨带权图中单源最短路径的基础算法——Bellman-Ford以及它如何处理Prim和Kruskal无法应对的负权边挑战。
【算法分析与设计】第13篇：最小生成树：Prim算法与Kruskal算法的比较研究
假设你是一家电信公司的工程师负责在若干城市之间铺设光缆。任意两座城市之间铺设光缆的成本已知你的目标是用最小的总成本将所有城市连通。这个问题抽象为图论语言就是给定连通无向图 G(V,E)G(V,E)每条边有权重 w(u,v)w(u,v)找出一个连通所有顶点的无环子图即一棵生成树且边权总和最小。这就是最小生成树问题。最小生成树是贪心算法成功应用的典型案例。但贪心为何在这个问题上总是对的答案藏在一条看似平凡却内涵深刻的定理之中。一、安全边定理贪心选择的正确性基石将最小生成树问题的贪心策略统一在一个理论框架下是理解所有生成树算法的关键。这个框架的核心是安全边定理。设无向连通图 G(V,E)G(V,E)权重函数为 ww。设 AA 是某棵最小生成树的边子集初始可为空。若存在 GG 的一个割 (S,V−S)(S,V−S)使得割尊重 AA即 AA 中没有边跨越该割边 (u,v)(u,v) 是跨越该割的所有边中权重最小的一条即轻量级边则 (u,v)(u,v) 对于 AA 是安全的——将其加入 AA 后AA 仍然是某棵最小生成树的子集。这条定理的证明并不复杂。设 TT 是包含 AA 的一棵最小生成树。若 (u,v)∈T(u,v)∈T则命题成立。若 (u,v)∉T(u,v)∈/T由于 TT 连通TT 中必存在路径连接 uu 和 vv该路径上必有一条边 (x,y)(x,y) 跨越割 (S,V−S)(S,V−S)。将 (u,v)(u,v) 加入 TT 会形成环删除 (x,y)(x,y) 则打破环并恢复树结构。由轻量级边的定义知 w(u,v)≤w(x,y)w(u,v)≤w(x,y)新树的权重不大于 TT故仍为最小生成树且包含 A∪{(u,v)}A∪{(u,v)}。证毕。安全边定理不仅给出了贪心策略的理论保证更揭示了两种经典的算法设计路径Prim算法每次维护一个不断增长的顶点集合 SS在连接 SS 与 V−SV−S 的割中选最小边Kruskal算法则按全局边权排序每次选一条不会形成环的最小边——这两者均满足安全边定理的条件只是割的选择方式不同。二、Prim算法围绕顶点集的生长策略Prim算法将生成树从一个根顶点开始逐步“生长”。初始时 S{r}S{r}A∅A∅。每一步在连接 SS 与 V−SV−S 的所有边中选一条权重最小的将其加入 AA并将该边在 V−SV−S 中的端点加入 SS。重复直到 SVSV。高效的实现依赖最小优先队列。对每个顶点 v∈V−Sv∈V−S维护一个键值 key[v]key[v]表示当前连接 vv 与 SS 中任意顶点的最小边权。每轮从优先队列中取出键值最小的顶点 uu将其加入 SS然后检查 uu 的所有邻边 (u,v)(u,v)若 v∈V−Sv∈V−S 且 w(u,v)key[v]w(u,v)key[v]则更新 key[v]key[v] 并调整优先队列。若优先队列以二叉堆实现则每次取最小键值操作为 O(logn)O(logn)每条边至多触发一次键值更新也是 O(logn)O(logn)总复杂度为 O(mlogn)O(mlogn)。若采用斐波那契堆键值更新的平摊代价降至 O(1)O(1)总复杂度可优化至 O(mnlogn)O(mnlogn)。不过在工程实践中二叉堆版本因其常数因子小且实现简单仍是主流选择。三、Kruskal算法全局贪心的边排序策略Kruskal算法采取截然不同的视角它不再专注于某个不断扩张的连通区域而是将全部边按权重从小到大排序依次检查每条边——若当前边连接两个不同的连通分量则将其加入生成树否则舍弃。当生成树包含 n−1n−1 条边时算法终止。判断一条边是否连接不同连通分量的数据结构是并查集。初始时每个顶点自成一集合。检查边 (u,v)(u,v) 时调用 Find(u)Find(u) 与 Find(v)Find(v) 判断二者是否同属一个集合若不同则执行 Union(u,v)Union(u,v) 合并两个集合并将该边加入 AA。采用按秩合并和路径压缩两项优化后并查集的单次操作平摊代价几乎为常数准确界为 O(α(n))O(α(n))其中 αα 为反阿克曼函数在实践中可视为不超过4的常数。Kruskal算法的时间复杂度的主导项在于边排序——O(mlogm)O(mlogm)。并查集的操作总代价仅为 O(m⋅α(n))O(m⋅α(n))。由于 mO(n2)mO(n2) 且 logmO(logn)logmO(logn)整体复杂度可写为 O(mlogn)O(mlogn)。四、稀疏图与稠密图的适用性抉择Prim算法和Kruskal算法的渐进复杂度相同——均为 O(mlogn)O(mlogn)在二叉堆实现下。但常数因子和实际表现因图的稠密程度而异。对于稀疏图mΘ(n)mΘ(n)Kruskal算法往往更优。排序的 O(mlogm)O(mlogm) 实际开销有限且并查集的操作极其轻量。Prim算法则需要维护优先队列堆操作的常数因子相对较大。对于稠密图mΘ(n2)mΘ(n2)Prim算法的简单版本甚至可以不用堆仅维护一个数组记录每个顶点到当前 SS 的最小边权每轮暴力扫描所有顶点找到最小值总复杂度 O(n2)O(n2)。当 m≈n2m≈n2 时O(n2)O(n2) 优于 O(mlogn)O(mlogn)。因此稠密图场景下Prim的朴素实现反而是实用的选择。此外Kruskal算法的优势在于它天然适合处理边集不完整给出的情形——只要边按权重的排序流式可用算法便可逐步推进。Prim算法则要求图在内存中以邻接结构存储更适合随机访问顶点邻边的场景。五、理论延伸与应用最小生成树不仅是网络设计的基础工具也在更广泛的算法领域扮演支撑角色。在近似算法中旅行商问题的Christofides算法以最小生成树为起点构造近似解达到了3/2的近似比。在聚类分析中对数据集构建以距离为权重的完全图其最小生成树的最长边决定了单链接聚类的合并阈值。从安全边定理出发Prim与Kruskal殊途同归。贪心策略之所以在这里成功本质上是因为最小生成树问题构成一个拟阵——我们在第8篇中论证过带权拟阵上的贪心算法必然得到最优解。这个视角的统一性正是理论计算机科学最令人着迷之处。下一篇我们将从生成树转向路径问题探讨带权图中单源最短路径的基础算法——Bellman-Ford以及它如何处理Prim和Kruskal无法应对的负权边挑战。
