2021-04-19：手写代码：最小生成树算法之Kruskal。
福大大 答案2021-04-19：
并查集。边从小到大，找最小边，无环。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
graph := &Graph{}
graph.nodes = make(map[int]*Node)
graph.nodes[0] = &Node{}
graph.nodes[1] = &Node{}
graph.nodes[2] = &Node{}
graph.edges = make(map[*Edge]struct{})
graph.edges[&Edge{weight: 22, from: graph.nodes[0], to: graph.nodes[1]}] = struct{}{}
graph.edges[&Edge{weight: 33, from: graph.nodes[1], to: graph.nodes[2]}] = struct{}{}
graph.edges[&Edge{weight: 11, from: graph.nodes[2], to: graph.nodes[0]}] = struct{}{}
ret := kruskalMST(graph)
fmt.Println("结果：")
for a, _ := range ret {
fmt.Println(a.weight)
}
}
type Edge struct {
weight int
from *Node
to *Node
}
// 点结构的描述
type Node struct {
value int
in int
out int
nexts []*Node
edges []*Edge
}
type Graph struct {
nodes map[int]*Node
edges map[*Edge]struct{}
}
func printPriorityQueue(priorityQueue []*Edge) {
for _, edge := range priorityQueue {
fmt.Println(edge.weight)
}
}
func kruskalMST(graph *Graph) map[*Edge]struct{} {
unionFind := &UnionFind{}
unionFind.makeSets(graph.nodes)
// 从小的边到大的边，依次弹出，小根堆！
priorityQueue := make([]*Edge, 0)
for edge, _ := range graph.edges {
priorityQueue = append(priorityQueue, edge)
}
fmt.Println("排序前：")
printPriorityQueue(priorityQueue)
//排序
sort.SliceStable(priorityQueue, func(i int, j int) bool {
return priorityQueue[i].weight > priorityQueue[j].weight
})
fmt.Println("--------")
fmt.Println("排序后：")
printPriorityQueue(priorityQueue)
fmt.Println("--------")
result := make(map[*Edge]struct{})
for len(priorityQueue) > 0 { // M 条边
edge := priorityQueue[len(priorityQueue)-1]
priorityQueue = priorityQueue[0 : len(priorityQueue)-1]
if !unionFind.isSameSet(edge.from, edge.to) { // O(1)
result[edge] = struct{}{}
unionFind.union(edge.from, edge.to)
}
}
return result
}
type UnionFind struct {
// key 某一个节点， value key节点往上的节点
fatherMap map[*Node]*Node
// key 某一个集合的代表节点, value key所在集合的节点个数
sizeMap map[*Node]int
}
func (this *UnionFind) makeSets(nodes map[int]*Node) {
this.fatherMap = make(map[*Node]*Node)
this.sizeMap = make(map[*Node]int)
for _, node := range nodes {
this.fatherMap[node] = node
this.sizeMap[node] = 1
}
}
func (this *UnionFind) findFather(n *Node) *Node {
path := make([]*Node, 0)
for n != this.fatherMap[n] {
path = append(path, n)
n = this.fatherMap[n]
}
for len(path) > 0 {
this.fatherMap[path[len(path)-1]] = n
path = path[0 : len(path)-1]
}
return n
}
func (this *UnionFind) isSameSet(a *Node, b *Node) bool {
return this.findFather(a) == this.findFather(b)
}
func (this *UnionFind) union(a *Node, b *Node) {
if a == nil || b == nil {
return
}
aDai := this.findFather(a)
bDai := this.findFather(b)
if aDai != bDai {
aSetSize := this.sizeMap[aDai]
bSetSize := this.sizeMap[bDai]
if aSetSize <= bSetSize {
this.fatherMap[aDai] = bDai
this.sizeMap[bDai] = aSetSize + bSetSize
delete(this.sizeMap, aDai)
} else {
this.fatherMap[bDai] = aDai
this.sizeMap[aDai] = aSetSize + bSetSize
delete(this.sizeMap, bDai)
}
}
}
执行结果如下：
左神java代码
