Kruskal最小生成树算法详解（Go语言实现图论经典算法）

算法步骤

1. 将图中所有边按权重从小到大排序。
2. 初始化一个空的生成树。
3. 依次遍历排序后的边：
• 如果当前边的两个顶点不在同一个连通分量中（即加入后不会形成环），则将该边加入生成树。
• 否则跳过该边。
4. 重复第3步，直到生成树包含 n-1 条边（n 为顶点数）。

关键工具：并查集（Union-Find）

为了高效判断两个顶点是否属于同一连通分量，Kruskal算法通常配合并查集（Union-Find）数据结构使用。并查集支持两种操作：

• Find(x)：查找元素 x 所在集合的根节点。
• Union(x, y)：合并 x 和 y 所在的集合。

Go语言实现

下面是一个完整的 Go 语言实现，包含并查集和 Kruskal 算法主体逻辑。

package mainimport (	"fmt"	"sort")// Edge 表示图中的一条边type Edge struct {	Src, Dst, Weight int}// Graph 表示一个无向图type Graph struct {	Vertices int	Edges    []Edge}// UnionFind 并查集结构type UnionFind struct {	parent []int	rank   []int}// NewUnionFind 初始化并查集func NewUnionFind(n int) *UnionFind {	parent := make([]int, n)	rank := make([]int, n)	for i := 0; i < n; i++ {		parent[i] = i		rank[i] = 0	}	return &UnionFind{parent: parent, rank: rank}}// Find 查找根节点（路径压缩优化）func (uf *UnionFind) Find(x int) int {	if uf.parent[x] != x {		uf.parent[x] = uf.Find(uf.parent[x])	}	return uf.parent[x]}// Union 合并两个集合（按秩合并优化）func (uf *UnionFind) Union(x, y int) {	rx, ry := uf.Find(x), uf.Find(y)	if rx == ry {		return	}	if uf.rank[rx] < uf.rank[ry] {		uf.parent[rx] = ry	} else if uf.rank[rx] > uf.rank[ry] {		uf.parent[ry] = rx	} else {		uf.parent[ry] = rx		uf.rank[rx]++	}}// Kruskal 实现 Kruskal 最小生成树算法func Kruskal(g Graph) []Edge {	// 按权重对边排序	sort.Slice(g.Edges, func(i, j int) bool {		return g.Edges[i].Weight < g.Edges[j].Weight	})	uf := NewUnionFind(g.Vertices)	mst := []Edge{}	for _, edge := range g.Edges {		if uf.Find(edge.Src) != uf.Find(edge.Dst) {			uf.Union(edge.Src, edge.Dst)			mst = append(mst, edge)			// 如果已经选了 n-1 条边，提前退出			if len(mst) == g.Vertices-1 {				break			}		}	}	return mst}func main() {	// 示例图：5个顶点	g := Graph{		Vertices: 5,		Edges: []Edge{			{0, 1, 10},			{0, 2, 6},			{0, 3, 5},			{1, 3, 15},			{2, 3, 4},			{2, 4, 8},			{3, 4, 9},		},	}	mst := Kruskal(g)	fmt.Println("最小生成树的边：")	totalWeight := 0	for _, e := range mst {		fmt.Printf("%d -- %d == %d\n", e.Src, e.Dst, e.Weight)		totalWeight += e.Weight	}	fmt.Printf("总权重：%d\n", totalWeight)}

运行结果说明

以上代码输出如下：

最小生成树的边：2 -- 3 == 40 -- 3 == 50 -- 1 == 102 -- 4 == 8总权重：27

时间复杂度分析

Kruskal算法的时间复杂度主要由排序决定，为 O(E log E)，其中 E 是边的数量。并查集操作接近常数时间（使用路径压缩和按秩合并优化后），因此整体效率很高，特别适合稀疏图（边数远小于顶点数平方的图）。

总结

通过本教程，你已经掌握了Kruskal算法的核心思想、实现细节以及在Go语言中的完整编码方式。无论是学习图论算法还是准备面试，理解并能手写 Kruskal 都是非常有价值的技能。希望你能动手实践，加深理解！

关键词回顾：Kruskal算法、最小生成树、Go语言实现、图论算法。