最小生成树：Prim 与 Kruskal 算法

什么是最小生成树？

在无向连通图中，生成树是包含所有顶点且无环的连通子图，恰好有 V-1 条边（V 为顶点数）。最小生成树（Minimum Spanning Tree, MST） 是这些生成树中边权重之和最小的那一棵。

核心特性

• 包含图中所有 N 个顶点，恰好有 N-1 条边。
• 不存在环路。
• 总边权最小（可能有多个并列的 MST）。
• 若图中存在权重相同的边，MST 可能不唯一。

应用场景

• 网络布线成本最小化（城市间光缆铺设）。
• 电路板连通所有节点的最短连线。
• 图像分割、聚类分析中的数据点连接。

两条核心性质

理解 MST 算法前，需要掌握两条贪心选择性质：

Prim 算法基于割性质；Kruskal 算法基于环性质。两者都是贪心算法，只是一层一层推进的方式不同。

Prim 算法

Prim 算法像“从一点生长出整棵树”：每次从已连通顶点集与未连通顶点集之间的边中，选择一条权重最小的边，将新顶点纳入树中。

算法步骤

1. 初始化 visited 集合为空（或标记所有顶点未访问），随机选一个起点标记为已访问。
2. 维护一个优先队列（最小堆），存放连接“已访问”与“未访问”集合的所有边。
3. 重复直到所有顶点都被访问：
   • 从堆中取出权重最小的边 (u, v, w)，其中 u 已访问，v 未访问。
   • 若 v 未访问，则将该边加入 MST，标记 v 为已访问，并将 v 的所有邻接边 (v, x, weight) 中 x 未访问的边入堆。
4. 若堆空但还有顶点未访问，说明图不连通。

伪代码（邻接表 + 最小堆）

MST_PRIM(graph, start):
    mst_edges = []
    total_weight = 0
    visited = set([start])
    pq = MinHeap()
    将 start 的所有邻边入堆

    while pq 非空 and visited 数量 < V:
        weight, u, v = pq.pop()
        if v 已在 visited:
            continue
        visited.add(v)
        mst_edges.append((u, v, weight))
        total_weight += weight
        for (neighbor, w) in graph[v]:
            if neighbor 不在 visited:
                pq.push((w, v, neighbor))

    if visited 数量 != V:
        return 图不连通
    return mst_edges, total_weight

复杂度

• 使用二叉堆：O((V+E) log V)，适合稠密图。
• 使用斐波那契堆可优化至 O(E + V log V)。
• 使用邻接矩阵的朴素实现 O(V²)，在小规模稠密图上更简单。

直观示例

假设图如下（边：权重）：

A—1—B
|    /|
2   4 3
| /   |
C—5— D

从 A 开始：

1. 挑出 A-B(1) → 加入 B。
2. 待选边：A-C(2), B-C(4), B-D(3)。
3. 选最小 A-C(2) → 加入 C。（割性质）
4. 待选边：B-C(4), B-D(3), C-D(5)。选 B-D(3) → 加入 D。 得到 MST 边：A-B(1), A-C(2), B-D(3)，总权 6。

Kruskal 算法

Kruskal 算法将边按权重升序排序，依次加入最小边，但绝不形成环。它基于环性质，使用并查集（Union-Find）高效判环。

算法步骤

1. 将所有边按权重升序排序。
2. 初始化并查集，每个顶点自成一个集合。
3. 遍历排序后的每一条边 (u, v, weight)：
   • 若 u 和 v 属于不同集合（即加入该边不形成环），则将该边加入 MST，并合并两集合。
   • 若已选够 V-1 条边，则提前终止。
4. 若最终选边数少于 V-1，图不连通。

伪代码

MST_KRUSKAL(graph):
    edges = 图中所有边的列表
    对 edges 按 weight 升序排序
    uf = UnionFind(V)
    mst_edges = []
    total_weight = 0

    for each (u, v, weight) in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_edges.append((u, v, weight))
            total_weight += weight
            if len(mst_edges) == V - 1:
                break

    if len(mst_edges) != V - 1:
        return 图不连通
    return mst_edges, total_weight

复杂度

• 排序 O(E log E)，并查集操作接近 O(α(V))，总体 O(E log E)。
• 适合稀疏图（边数接近 V），尤其 E = O(V) 时非常高效。

直观示例

用之前同一张图，边排序：A-B(1), A-C(2), B-D(3), B-C(4), C-D(5)。

1. 选 A-B，集合：{A,B}, {C}, {D}
2. 选 A-C，集合：{A,B,C}, {D}
3. B-D(3) 两端不同集合，加入，合并后全集连通。
4. 已达 3 = V-1 条边，停止。MST 与 Prim 结果相同。

Prim vs Kruskal：如何选择？

经验法则

• 邻接矩阵 + 朴素 Prim 在处理 V ≤ 5000 的稠密图时简单快速。
• 邻接表 + 堆优化 Prim 通用性好。
• 边数较少（比如平面图）用 Kruskal 更直接，代码也短。

常见疑问

Q1：图中有负权边怎么办？
最小生成树只关心相对顺序，负权边不影响算法正确性，Prim 和 Kruskal 都能处理。

Q2：最大生成树如何求？
将边权重取负，或者将“取最小”改为“取最大”即可。

Q3：如果边权全部相同，任一生成树都是 MST？
是的，此时 Prim 和 Kruskal 可能会产生不同结构的 MST，但总权重相等。

Q4：不连通图能求最小生成森林吗？
可以。Kruskal 天然会生成最小生成森林；Prim 需对每个连通分量分别运行。

手把手代码示例（Python）

为便于理解，附上简化版实现（无堆/并查集优化，聚焦逻辑）：

Prim 简化版（邻接矩阵 O(V²)）

def prim_mst(graph, V):
    # graph 为邻接矩阵，graph[u][v] = 权重，无边则为 INF
    INF = 10**9
    selected = [False] * V
    min_edge = [INF] * V   # 每个未选顶点到已选树的最小边权重
    min_edge[0] = 0
    parent = [-1] * V

    for _ in range(V):
        u = -1
        for i in range(V):
            if not selected[i] and (u == -1 or min_edge[i] < min_edge[u]):
                u = i
        if min_edge[u] == INF:
            return "图不连通"

        selected[u] = True
        for v in range(V):
            if graph[u][v] != INF and not selected[v] and graph[u][v] < min_edge[v]:
                min_edge[v] = graph[u][v]
                parent[v] = u

    # 输出 MST 边
    for i in range(1, V):
        print(f"{parent[i]} - {i}  权: {graph[parent[i]][i]}")

Kruskal 简化版（并查集 + 排序）

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(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):
        self.parent[self.find(x)] = self.find(y)

def kruskal_mst(edges, V):
    # edges 为列表，元素 (u, v, weight)
    edges.sort(key=lambda x: x[2])
    ds = DisjointSet(V)
    mst = []
    total = 0
    for u, v, w in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, w))
            total += w
            if len(mst) == V - 1:
                break
    if len(mst) < V - 1:
        return "图不连通"
    for u, v, w in mst:
        print(f"{u} - {v}  权: {w}")

总结

• 最小生成树是连通带权图的关键结构，工具有 Prim 和 Kruskal。
• Prim 逐步生长，适合稠密图，用堆优化。
• Kruskal 全局排序边，适合稀疏图，依赖并查集。
• 理解“割性质”与“环性质”能更好掌握贪心正确性。

现在你可以根据图的稠密程度选择算法，去解决实际网络优化问题了。