Kruskal 最小生成树

图

说明

按边权排序并跳过会形成环的边；并查集判断两端是否已连通。

分析

把所有边按权重升序排列，依次尝试加入；如果两端已在同一并查集，就跳过这条会形成环的边。选到 V−1 条边时得到生成树。

图解推演

三条边按权重 1、2、5 排序：先选 1—2，再选 0—1，总代价 3。此时 0 与 2 已在同一集合，权重 5 的边会闭环，因此不选。并查集只回答连通性，排序与割性质共同保证最小代价，不能按输入顺序随意选边。

查看图表代码

适用前提与边界

图不连通时无法得到单棵生成树，示例返回 −1。

示例输入与调用

fmt.Println(Kruskal(3, []Edge{{0, 1, 2}, {1, 2, 1}, {0, 2, 5}}))

运行输出

3

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

type Edge struct{ U, V, W int }

func Kruskal(n int, edges []Edge) int {
	sort.Slice(edges, func(i, j int) bool { return edges[i].W < edges[j].W })
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	total := 0
	count := 0
	for _, e := range edges {
		a, b := find(e.U), find(e.V)
		if a != b {
			parent[a] = b
			total += e.W
			count++
		}
	}
	if count != n-1 {
		return -1
	}
	return total
}

func main() {
	fmt.Println(Kruskal(3, []Edge{{0, 1, 2}, {1, 2, 1}, {0, 2, 5}}))
}