Prim 最小生成树

图

说明

从已选顶点向外选最轻的边；下例使用邻接矩阵，时间 O(V²)。

分析

从任意顶点开始，维护每个未入树顶点连接到当前树的最便宜边。每轮加入代价最低者，并更新它邻居的候选代价。

图解推演

从 0 开始，候选连边为到 1 的 2、到 2 的 5；选入 1 后，到 2 的最便宜连边改为 1，因此总权重为 3。这里记录的是接入树的一条边的权重，不能像 Dijkstra 那样累计源点路径距离。每次选择必须跨越已入树与未入树的边界。

查看图表代码

适用前提与边界

示例用邻接矩阵与 O(V²) 扫描；负值表示没有边，矩阵必须为方形。合法边权及总权重须能用本机 int 表示，最大 int 保留为不可达哨兵；稀疏图通常用优先队列和邻接表。

示例输入与调用

fmt.Println(Prim([][]int{{-1, 2, 5}, {2, -1, 1}, {5, 1, -1}}))

运行输出

3

完整 Go 示例

package main

import "fmt"

func Prim(weight [][]int) int {
	n := len(weight)
	if n == 0 {
		return 0
	}
	inf := int(^uint(0) >> 1)
	used := make([]bool, n)
	best := make([]int, n)
	for i := range best {
		best[i] = inf
	}
	best[0] = 0
	total := 0
	for range n {
		v := -1
		for i := range n {
			if !used[i] && (v < 0 || best[i] < best[v]) {
				v = i
			}
		}
		if v < 0 || best[v] == inf {
			return -1
		}
		used[v] = true
		total += best[v]
		for w, c := range weight[v] {
			if !used[w] && c >= 0 && c < best[w] {
				best[w] = c
			}
		}
	}
	return total
}

func main() {
	fmt.Println(Prim([][]int{{-1, 2, 5}, {2, -1, 1}, {5, 1, -1}}))
}