更多优质内容
请关注公众号

算法小白的入门日记(二十)图的连通性问题——最小生成树算法-张柏沛IT博客

正文内容

算法小白的入门日记(二十)图的连通性问题——最小生成树算法

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-23 11:22 浏览量:1245
本系列文章目录
展开/收起

 最小生成树算法

最小生成树算法的作用是将一个图的多余边去除,使得图中所有顶点满足连通性的同时,边的权重总和最小,此时这个取出多余边的图我们称为最小连通子图,最小连通子图没有回路,因此是一个树形结构,又称为最小生成树。

如果我们将每条边看成是一个顶点到达另一个顶点的成本,最小生成树算法的目的是将整个图所有节点连通的成本最小化。而最短路径算法则是算出任意两个节点连通的最小成本。


例如一个图原本的样子是这样


变成最小生成树后是这样


最小生成树算法采用贪心算法

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]
}





更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(二十)图的连通性问题——最小生成树算法

热门推荐
推荐新闻