代码随想录day 56 || 图论6

Prim算法

应用场景是主要是找到一个无向连通图的最小生成树，即连接所有节点且权重总和最小的树

// prim三部曲
// 1， 找到距离当前最小树最近节点
// 2，节点入树
// 3，更新mindist


// 更新树
func updateMinDist(edges [][]int, node int) {
	for _, edge := range edges {
		if edge[0] == node && edge[2] < minDist[edge[1]]{ // 直连当前节点，并且距离更短
			minDist[edge[1]] = edge[2]
		}
	}
}

// 找到不在树中的最近节点
func GetMinNode() int {
	var minVal int = math.MaxInt
	var minNode int = -1 // 特殊标记一下，如果没有找到最近节点，说明树已经遍历完成
	for i, v := range minDist {
		if !used[i] && v < minVal {
			minVal = v
			minNode = i
		}
	}
	return minNode
}

Kruskal算法