Kruskal 和 Prim 如何构建最小生成树？

Question

Accepted Answer

**最小生成树 (MST)** 使用 **最小总边权重** 连接加权连通图的所有顶点，且不形成环。**Kruskal** 和 **Prim** 是两个经典的贪心算法。

## Kruskal（排序边 + 并查集）

按权重对所有边进行排序；添加不形成环的最便宜的边。

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim（用 min-heap 扩展树）

从任意顶点开始；重复添加离当前树最便宜的边。

## 比较

| | Kruskal | Prim |
|---|--------|------|
| 方法 | 排序边 + 并查集 | 从节点扩展 + 堆 |
| 时间 | O(E log E) | O(E log V) |
| 最适合 | 稀疏图 | 密集图 |

## 使用场景 / 注意事项

MST 用于 **网络设计** — 铺设电缆、水管、聚类。两种算法都是贪心的，在这里已被证明是最优的。Kruskal 需要并查集来高效地避免环。

## 为什么这很重要

MST 最小化连接所有事物的成本 — 直接适用于基础设施和网络布局。

这是贪心算法被证明最优的一个清晰案例，加强了贪心选择推理。

Kruskal 还展示了并查集，这是一种应用广泛的数据结构。

	Kruskal	Prim
方法	排序边 + 并查集	从节点扩展 + 堆
时间	O(E log E)	O(E log V)
最适合	稀疏图	密集图