最小生成树

📌 核心概念

最小生成树（MST）：连接所有顶点且边权和最小的树。

两种算法：

• Kruskal：边的角度，适合稀疏图，O(ElogE)
• Prim：点的角度，适合稠密图，O(ElogV)

🎯 经典应用

Go 代码

type UnionFind struct {
    parent []int
    rank   []int
}
 
func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := range uf.parent {
        uf.parent[i] = i
    }
    return uf
}
 
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(x, y int) bool {
    px, py := uf.Find(x), uf.Find(y)
    if px == py {
        return false
    }
    if uf.rank[px] < uf.rank[py] {
        px, py = py, px
    }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] {
        uf.rank[px]++
    }
    return true
}

---

返回：图算法