2021-04-19：手写代码：最小生成树算法之Kruskal。

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代码