更多优质内容
请关注公众号
请关注公众号
最小生成树算法
最小生成树算法的作用是将一个图的多余边去除，使得图中所有顶点满足连通性的同时，边的权重总和最小，此时这个取出多余边的图我们称为最小连通子图，最小连通子图没有回路，因此是一个树形结构，又称为最小生成树。
如果我们将每条边看成是一个顶点到达另一个顶点的成本，最小生成树算法的目的是将整个图所有节点连通的成本最小化。而最短路径算法则是算出任意两个节点连通的最小成本。
例如一个图原本的样子是这样
变成最小生成树后是这样
最小生成树算法采用贪心算法：
1、创建一个“已连通集合（已触达顶点集合）”用于存放已经遍历过并且加入到生成树的顶点。创建一个一维数组arr表示最小生成树，顶点 i 的父节点为 arr[i]。生成树arr有一个虚拟根节点 -1。
2、从图中任意选择一个顶点A加入到“已连通集合”，节点A作为 arr 的下标0，arr[0] = -1，即顶点A的父节点是虚拟节点 -1。
3、从“已连通集合”中选择一个from节点，要求from节点和from的未访问过的相邻节点to节点的距离最小。将to顶点加入到“已连通集合”和最小生成树中。
4、重复上述过程，直到原图的所有顶点都加入到“已连通集合”和最小生成树中。
所生成的最小生成树的边的条数 = 总顶点数 - 1 = n - 1
代码实现如下：
// 最小生成树算法
func buildMinTree(g [][]int) []int{
num := len(g) // 顶点数
minTree := make([]int, num)
visited := make(map[int]struct{}) // 已连通集合
curVext := 0 // 当前遍历到的，即将放入集合内的顶点
minTree[curVext] = -1 // 将 0 号节点放入集合中
visited[curVext] = struct{}{}
for len(visited) < num{
minWeight := math.MaxInt32 // 已连通集合的某节点 和 未连通的某节点 之间最小距离
var from, to int
for nextFromVext, _ := range(visited){ // 从已连通集合中选择一个from节点
for nextToVext:=0; nextToVext<num; nextToVext++{ // 从所有from节点的相邻节点选择一个未访问的且距离最小的to节点作为下一个生成树节点
if _, ok := visited[nextToVext]; !ok && g[nextFromVext][nextToVext] < minWeight{ // nextFromVext 到 nextToVext的距离小于 minWeight 既说明 这两个顶点是相邻的（因为他们的距离 比 MaxInt 小），又说明本nextToVext顶点比上一次的nextToVext顶点离 nextfromVext顶点近
from = nextFromVext
to = nextToVext
minWeight = g[nextFromVext][nextToVext]
}
}
}
visited[to] = struct{}{}
minTree[to] = from
}
return minTree
}
// 测试用例（用的是最短路径那个例子）
func TestBuildMinTree(t *testing.T) {
m := math.MaxInt32
matrix := [][]int{
{0,5,2,m,m,m,m},
{5,0,m,1,6,m,m},
{2,m,0,6,m,8,m},
{m,1,6,0,1,2,m},
{m,6,m,1,0,m,7},
{m,m,8,2,m,0,3},
{m,m,m,m,7,3,0},
}
fmt.Println(buildMinTree(matrix)) // [-1 0 0 1 3 3 5]
}
