最小生成树Prim与Kruskal算法

可视化演示

通过Prim选点法与Kruskal选边法的动画演示，直观展示贪心策略构建MST的过程，对比两种算法的复杂度与适用场景。

一、概念与定义

修路之前，村长得先看懂地图。地图上每个村庄是一个“顶点”，每一条候选路段是一条“边”，边上的数字就是修路造价。如果任意两个村庄之间都能通过若干条路互通，这张图就是“连通图”。在这张图上，哪怕删掉很多候选路段，只要保证所有村庄依然互相连通，剩下的路网仍然是一张连通图。

在候选路段中选出一部分来修，让所有村庄连通且不出现环路——这种结构在数学上正好是一棵树。图论把这种“连通所有顶点且无环”的子图称为生成树。一棵生成树恰好用最少的边把所有顶点串在一起，不多不少，刚刚好。

生成树有个铁律：n 个顶点的连通图，任意一棵生成树恰好有 n-1 条边。因为每多连通一个新顶点，只需要额外修一条路把它挂到已有网络里。

明白了这个铁律，村长心里就有底了：修 5 条路就能串起 6 个村庄。但省钱的学问在于——选哪 5 条？在所有可能的生成树中，边权总和最小的那一棵，就是最小生成树（MST）。

二、Prim选点法

Prim 的风格像“圈地扩张”。村长先把 0 号村划进自己地盘，然后趴在地上数：从地盘里任意村庄出发，到地盘外任意村庄，所有候选路中哪条最便宜？修它！把新村庄圈进来，继续看下一轮。地盘像滚雪球一样越滚越大，直到 6 个村庄全部被圈进来。

每一步，算法都维护两个集合——已选入生成树的顶点集合 S，和未进入的顶点集合 V-S。它要做的，就是在所有“跨过集合边界”的边里挑一条权重最小的。这就是贪心：每次只看眼前最优，但最终结果却是全局最优。村庄之间候选道路越多，这种“从边界向外圈地”的方式越能发挥威力。

贪心选择的数学表达如下：

实现上，朴素写法用邻接矩阵保存边权，每轮扫描所有顶点找最小边，总复杂度 O(V²)；更聪明的做法是用优先队列维护“边界候选边”，每次弹堆得到最小边，复杂度降到O(E log V)。Prim 特别适合边很多的稠密图——顶点虽多，但“从已圈区域向外延伸”的过程非常稳定。

三、Kruskal选边法

Kruskal 则像位精打细算的采购员。他把所有候选路段按造价从低到高排成一条长队，从最便宜的看起：这条路段的两端村庄目前还不连通？修！已经连通？跳过！理由很简单——修了就绕圈，纯属浪费。采购员头也不抬，一路看下去，直到修满 5 条路把 6 个村庄全部连通。

怎么快速判断两端是否连通？答案是并查集。它把每个村庄看作一个集合，初始时各自为政。处理边 (u, v) 时，若 find(u) 不等于 find(v)，说明两边还不通，可以修路；修完后把两个集合合并。并查集配合路径压缩，判断一次连通性几乎只要常数时间。

判环与选边的规则可以写成：

采购员从最便宜的慢慢看，修满 n-1 条路就收工。他从不关心连接顺序，只关心“这条边的价签”。所以当图里边的数量远少于点对数量（稀疏图）时，Kruskal 的排序选边法既简单又高效。

四、算法对比与选择

同样是修路，工具要按场景选。如果候选路段密密麻麻，几乎每个村庄之间都有路可选，这叫稠密图；反之如果只有零零散散几条路，叫稀疏图。村长和采购员各有各的强项，关键看地图长什么样。

两种算法的复杂度对比是核心决策依据：

当图稠密时 E 接近 V²，Kruskal 的 E log E 会显著变大，Prim 的邻接矩阵版 O(V²) 反而更稳定；当图稀疏时 E 接近 V，两者差别不大，但 Kruskal 实现简单、只需边集，通常更受工程偏爱。就像搬家：东西少叫小货车，东西多叫大卡车——不是谁好谁坏，而是看你的图是“瘦”还是“胖”。

五、实际应用

最小生成树可不只用来给村庄修路。凡是“互相连通 + 总成本最低”的问题，它都能插一脚：通信基站之间拉光纤、数据中心布网线、城市之间铺自来水管，都能套用这棵“省钱的树”。它的应用场景往往藏在我们看不见的基建图纸里。

在 AI 领域，MST 是单链接聚类的核心工具：把数据点当村庄、点间距离当造价，先构建一棵最小生成树，再砍断最长的若干条边，剩下的连通块就是簇。它不像 K-means 那样要求簇是“圆球状”，能识别任意形状的簇，因此在图像分割、社区发现中很有价值。

刻画 MST 与聚类关系的核心性质是切割性质：

切割性质像“围墙选址”的智慧：无论你在地图上怎么画圈，从圈内跨到圈外的最小造价道路，一定值得出现在某个最优方案里。正是这条性质，从根本上保证了贪心算法每一步都不会选错边。

六、实现与优化

拿到算法思路后，真刀真枪地写代码，还需要选对“工具箱”。Prim 的关键动作是“快速取出当前最小边”——优先队列（堆）是天然选择；Kruskal 的关键动作是“快速判断两点是否连通”——并查集上场。选对数据结构，代码的简洁度和性能截然不同。

并查集的核心是 find 函数，它返回节点所在集合的代表。朴素实现可能很慢，但配合路径压缩——找到祖先顺便把沿途节点直接挂到祖先下面——之后每次查询几乎都是 O(1)。递推式如下：

工程实现中，Prim 用邻接表存图、用堆存 (distance, vertex) 对；Kruskal 用边集三元组 (u, v, w) 排序，再配合并查集判环。若图本身不连通，两种算法都应在选不满 V-1 条边时返回“不存在最小生成树”。选对了工具，村长和采购员——也就是 Prim 与 Kruskal——都能把修路这件事办得又快又稳。

AI 应用场景

Python 演示

import heapq  class UnionFind:    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):        rx = self.find(x)        ry = self.find(y)        if rx == ry:            return False        if self.rank[rx] < self.rank[ry]:            self.parent[rx] = ry        elif self.rank[rx] > self.rank[ry]:            self.parent[ry] = rx        else:            self.parent[ry] = rx            self.rank[rx] += 1        return True  def kruskal(vertices, edges):    uf = UnionFind(len(vertices))    mst = []    total = 0    for u, v, w in sorted(edges, key=lambda x: x[2]):        if uf.union(u, v):            mst.append((u, v, w))            total += w    return mst, total  def prim(vertices, adj):    n = len(vertices)    visited = [False] * n    pq = [(0, 0, -1)]    mst = []    total = 0    while pq:        w, u, p = heapq.heappop(pq)        if visited[u]:            continue        visited[u] = True        total += w        if p != -1:            mst.append((p, u, w))        for v, w2 in adj[u]:            if not visited[v]:                heapq.heappush(pq, (w2, v, u))    return mst, total  if __name__ == '__main__':    vertices = [0, 1, 2, 3, 4, 5]    edges = [        (0, 1, 6), (0, 2, 3), (0, 4, 5),        (1, 2, 4), (1, 3, 7), (2, 3, 8),        (2, 4, 2), (2, 5, 5), (3, 5, 9), (4, 5, 4)    ]    mst_k, cost_k = kruskal(vertices, edges)    print('Kruskal 选中的边:', mst_k)    print('Kruskal 总造价:', cost_k)     adj = [[] for _ in vertices]    for u, v, w in edges:        adj[u].append((v, w))        adj[v].append((u, w))    mst_p, cost_p = prim(vertices, adj)    print('Prim 选中的边:', mst_p)    print('Prim 总造价:', cost_p)

1. sorted(edges, key=lambda x: x[2])按边权从小到大排序，这是 Kruskal 的核心第一步。
2. uf.union(u, v)尝试合并两个端点所在集合，返回 False 说明成环、边被跳过。
3. heapq.heappop(pq)从优先队列取出当前最小边，Prim 每次扩张都靠它。
4. if visited[u]: continue跳过已选入生成树的顶点，避免重复处理。
5. mst.append((p, u, w))记录选中边的两个端点和权重，构成最终生成树。

常见误区

面试题