最小生成树模板

一句话说明

最小生成树最常用的模板就是 Kruskal：边按权重从小到大选，只要不会成环就加入答案。

先判断它是不是 MST 题

最小生成树的目标是：

• 用 n-1 条边把所有点连起来
• 总边权和最小

它和最短路径不是一回事。
最短路径关心一对点之间最省，最小生成树关心整张图总连通成本最低。

Go 模板：Kruskal

type MSTEdge struct {
    Weight int
    From   int
    To     int
}
 
type UnionFind struct {
    parent []int
    size   []int
}
 
func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size}
}
 
func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}
 
func (uf *UnionFind) Union(a, b int) bool {
    ra, rb := uf.Find(a), uf.Find(b)
    if ra == rb {
        return false
    }
 
    if uf.size[ra] < uf.size[rb] {
        ra, rb = rb, ra
    }
    uf.parent[rb] = ra
    uf.size[ra] += uf.size[rb]
    return true
}
 
func Kruskal(nodeCount int, edges []MSTEdge) (int, []MSTEdge, bool) {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].Weight < edges[j].Weight
    })
 
    uf := NewUnionFind(nodeCount)
    total := 0
    selected := []MSTEdge{}
 
    for _, e := range edges {
        if !uf.Union(e.From, e.To) {
            continue
        }
        total += e.Weight
        selected = append(selected, e)
        if len(selected) == nodeCount-1 {
            return total, selected, true
        }
    }
 
    if nodeCount <= 1 {
        return 0, nil, true
    }
    return 0, nil, false
}

这个模板的核心逻辑

每次考虑当前最小边：

• 如果两端已经连通，就跳过
• 如果两端还没连通，就加入生成树

并查集的作用就是快速判断这条边会不会成环。

为什么它是对的

Kruskal 的贪心直觉是：

• 当前还能选的最小边
• 只要不会成环
• 选它就不会吃亏

这就是最小生成树的经典切分性质。

易错点

最小生成树模板最容易错的地方

• MST 只适用于无向图。
• 结果必须恰好选到 n-1 条边，否则图不连通。
• 最短路径树和最小生成树目标不同，不能混用。

复杂度

指标	复杂度
时间复杂度	O(E log E)
空间复杂度	O(V)

相关主题

• 图算法
• 并查集模板

---

返回：算法模板