最小生成树详解：Kruskal 与 Prim 算法

最小生成树解决什么问题

假设你要用电缆连接几栋楼，用公路连接几个城镇，或用网络链路连接几台服务器，每条可能的连接都有成本。你希望所有地点（直接或间接）互相连通，且总成本最低。形成回路的多余连接永远不需要，所以答案是一棵树：V 个节点恰好由 V − 1 条边连接。这棵树就是最小生成树。

最小生成树不是最短路径树。它最小化的是所有边的总权，而不是从某个起点到其他节点的距离。

为什么贪心选择是对的：割性质

把节点分成任意两组。在横跨两组的边中，最轻的那条一定属于某棵最小生成树。两种算法都依赖这一事实：

如果所有边权互不相同，最小生成树就是唯一的，两种算法会返回同一棵树。边权有相同值时，可能存在多棵总权相同的最小生成树。

逐步演示一个例子

无向图含 5 个节点，边为 A–B 4、A–C 3、B–C 1、B–D 2、C–D 4、D–E 2、C–E 5。

Kruskal 算法，边按权重排序：

从 A 出发的 Prim 算法：离开 {A} 的最便宜的边是 A–C（3）；从 {A, C} 出发是 C–B（1）；从 {A, B, C} 出发是 B–D（2）；从 {A, B, C, D} 出发是 D–E（2）。得到同一棵树，总权为 3 + 1 + 2 + 2 = 8。

Python 实现 Kruskal 算法

并查集为每个节点保存一个父指针。find 返回某节点所在连通分量的代表元，两个节点当且仅当代表元相同时才连通。

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

完整的并查集还会使用按秩或按大小合并，以保持树较浅。仅用路径减半在实践中就已经很快。当树已有 V − 1 条边时，可以提前结束循环。

Python 实现 Prim 算法

Prim 算法需要邻接表。它像 Dijkstra 算法一样使用惰性删除：把每条离开树的边都压入堆，并跳过远端节点已在树中的边。

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

时间与空间复杂度

因为 E 至多为 V²，所以 log E 至多为 2 log V，O(E log E) 和 O(E log V) 是同一量级。

变体与常见错误

• 非连通图：不存在生成树。此时 Kruskal 返回最小生成森林（每个连通分量一棵树）；从单个起点出发的 Prim 只覆盖该起点所在的连通分量。请检查树是否有 V − 1 条边。
• 最大生成树：把边按降序排序（或对权取负）。两种算法都允许负权。
• 有向图需要另一种算法（最小树形图，Chu-Liu/Edmonds 算法）；Kruskal 和 Prim 不适用。
• 聚类：运行 Kruskal，剩下 k 个连通分量时停止，结果就是分成 k 组的单链接聚类。
• Borůvka 算法（1926 年）同时为每个连通分量加入其最便宜的边，非常适合并行化。

何时使用及实际应用

• 网络设计：只要任何连通方案都可接受，就用它找出用电缆、管道或公路连接各站点的最便宜方式。
• 近似算法：对度量旅行商问题，最小生成树可给出长度不超过最优解两倍的环游路线。
• 聚类与图像分割：切掉最小生成树中最重的边。
• 面试题：连接所有点的最小费用、最低成本联通所有城市、优化水资源分配。