Go Gonum graph 怎样构造无向图最小生成树

在 Go Gonum 中构造无向图最小生成树，核心不是自己实现排序和并查集，而是先用 simple.WeightedUndirectedGraph 保存带权边，再把一个空的目标图传给 path.Prim。函数会把最小生成树写入目标图，并返回树边权重之和；如果原图不连通，返回的是最小生成森林的总权重。

官方地址：https://pkg.go.dev/gonum.org/v1/gonum/graph/path

本文使用 Gonum v0.17.0 的 graph/path 与 graph/simple 接口，示例只关注“带权无向图如何得到树边”这一件事。

先把关系建成带权无向图

最小生成树的输入必须能表达两件事：节点之间是无向关系，以及每条边有可比较的代价。Gonum 的 NewWeightedUndirectedGraph(self, absent) 用两个浮点参数表示自环权重和不存在边时的权重。常见写法是自环为 0、缺失边为正无穷。

go mod init example.com/gonum-mst

# 只引入示例使用的 Gonum 图算法模块
go get gonum.org/v1/gonum@v0.17.0

下面用五个节点模拟站点连接，权重可以代表距离、费用或链路延迟。代码中的中文注释说明了建图边界和目标图用途。

package main

import (
	"fmt"
	"math"

	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {
	// absent 使用正无穷，表示没有显式边时不能被当成低成本连接。
	g := simple.NewWeightedUndirectedGraph(0, math.Inf(1))

	addEdge := func(from, to int64, weight float64) {
		// NewWeightedEdge 保留两个端点和权重，SetWeightedEdge 写入无向图。
		g.SetWeightedEdge(g.NewWeightedEdge(simple.Node(from), simple.Node(to), weight))
	}

	addEdge(1, 2, 4)
	addEdge(1, 3, 1)
	addEdge(2, 3, 2)
	addEdge(2, 4, 5)
	addEdge(3, 4, 8)
	addEdge(3, 5, 10)
	addEdge(4, 5, 3)

	// 目标图必须是空图；Prim 会把选中的树边写入其中。
	tree := simple.NewWeightedUndirectedGraph(0, math.Inf(1))
	total := path.Prim(tree, g)

	fmt.Printf("total=%.0f\n", total)
	for edges := tree.WeightedEdges(); edges.Next(); {
		e := edges.WeightedEdge()
		fmt.Printf("%d-%d weight=%.0f\n", e.From().ID(), e.To().ID(), e.Weight())
	}
}

用 path.Prim 把树写入目标图

path.Prim(tree, g) 的第一个参数是输出目标，第二个参数是输入图。返回值是最小生成树的权重总和，不是树对象；因此要拿到具体边，必须继续遍历第一个参数。

上面的示例中，权重较小且能连接新节点的边会被保留，最终总权重为 11。边的遍历顺序不应当当作算法排序结果，业务代码只需要关心端点、权重以及总成本。

遍历 WeightedEdges 读取结果

目标图实现了 WeightedEdges()，迭代器返回的每一条边都可以通过 From()、To() 和 Weight() 读取。示例输出的总权重是稳定的，但边的打印顺序可能随图的内部遍历方式变化。

total=11
1-3 weight=1
2-3 weight=2
4-5 weight=3
2-4 weight=5

如果要把结果转换为业务结构，建议在遍历时立即复制成自己的边记录，而不是长期依赖 Gonum 目标图中的节点对象。尤其是节点类型是指针或引用语义时，算法文档说明输入图和输出图可能共享节点、边的值。

非连通图会返回最小生成森林

最小生成树要求所有节点属于同一个连通分量。Gonum 的 Prim 对非连通输入不会凭空补边，而是为各个连通分量构造最小生成树，合起来形成最小生成森林，并返回各棵树权重之和。

因此，生产代码不要只判断总权重是否大于零来确认“全图已经连通”。可以先根据业务的节点数量和目标图节点数量检查覆盖情况，或者在建图阶段明确记录连通分量。若必须拒绝非连通输入，应在调用算法前后增加业务层判断，而不是把 Prim 的返回值误解为连通性结论。

Prim 和 Kruskal 怎么选

path.Kruskal(dst, g) 同样会把结果写入目标图并返回总权重。两者的使用方式很接近：都需要一个空的 WeightedBuilder 目标图；差别主要在算法组织方式。Prim 从连通区域逐步扩展，Kruskal 按边的权重进行贪心合并。

• 已经有一个明确的连通起点或希望围绕连通区域扩展时，可以优先看 Prim。
• 更关注全局边集合，或者希望直接按边成本处理时，可以考虑 Kruskal。
• 边权相同会让最小生成树不一定唯一；总权重可以相同，具体树边组合可能不同。
• 输入包含负权边并不是最小生成树本身的禁区，但业务仍应确认权重含义，不能把距离、费用和收益混在同一尺度。

写入业务系统前的几个检查点

最小生成树适合网络铺设、道路连接、依赖关系压缩等场景，但它只优化“连接所有节点的边权总和”，不会自动满足容量、方向、可靠性或冗余要求。把结果落库或下发前，可以按下面的最小清单处理：

1. 确认输入是无向关系；有方向的依赖图不要直接套用无向算法。
2. 确认所有边的权重单位一致，并明确自环和缺失边的含义。
3. 为输出目标图使用全新的空图，避免目标图已有同 ID 节点触发冲突。
4. 读取实际树边后再做业务约束检查，不要只保存一个总权重。
5. 对非连通输入明确选择“接受森林”还是“拒绝任务”。

常见问题

为什么 Prim 的结果图不是原图的副本？

目标图只接收算法选中的树边，不会保留没有进入最小生成树的候选边。需要完整关系时应同时保存输入图和结果图。

权重相同会不会得到不同结果？

会。相同权重可能对应多棵同样最优的树，不能把一次遍历得到的边集合当成唯一答案；如果业务需要稳定输出，应在业务层设计稳定的边标识和排序规则。

可以用 Prim 求最短路径吗？

不可以。最小生成树关注全体节点的连接成本，最短路径关注指定起点和终点之间的路径，应使用 path.DijkstraFrom、path.DijkstraFromTo 等对应接口。

总结

Go Gonum 构造无向图最小生成树的最小步骤是：用 simple.NewWeightedUndirectedGraph 建立带权输入图，用另一个空图作为目标，调用 path.Prim，再通过 WeightedEdges() 读取树边。记住返回值是总权重，非连通图返回的是森林；如果要按全局边集合组织贪心合并，则可以换用 path.Kruskal。