Golang实现并查集

FredricZhu · · 1363 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

模拟C++实现了一个并查集，主要是理解连通图的原理。
main.go

package main

import (
    "fmt"

    "gitlab.sz.sensetime.com/zhuzhongliang/union_find_set/utils"
)

/*
** 今天是伊格那丢的生日。他邀请了很多朋友。现在该吃晚饭了。
** 伊格那丢想知道他至少需要多少张桌子。你必须注意到并不是所有的朋友都认识对方，
** 而且所有的朋友都不想和陌生人待在一起。这个问题的一个重要规则是如果我告诉你A认识B,
** B认识C，这意味着A, B, C互相认识，所以它们可以在一个表中。
** 例如:如果我告诉你A知道B, B知道C, D知道E，
** 那么A, B, C可以在一个表中，D, E必须在另一个表中。
 */

func main() {
    uSet := utils.NewUnionFindSet(1000)

    var relationNum int

    fmt.Printf("请输入一共有多少对关系:")
    fmt.Scanln(&relationNum)
    var a, b int
    for i := 0; i < relationNum; i++ {
        fmt.Println("请输入关系a:")
        fmt.Scanln(&a)
        fmt.Println("请输入关系b:")
        fmt.Scanln(&b)
        uSet.Mix(a, b)
    }

    tableNum := 0

    for i := 0; i < 1000; i++ {
        // 说明是根节点，需要加桌子
        if uSet.People[i] == i {
            tableNum++
        }
    }

    fmt.Printf("一共需要 %d 张桌子\n", tableNum)
}

utils/union_find_set.go

package utils

// UnionFindSet 并查集结构体
type UnionFindSet struct {
    People []int // 人员及其Header数组
    N      int   // 一共有多少人
}

func NewUnionFindSet(n int) *UnionFindSet {
    people := make([]int, n)
    // 让每一个人的父节点指向自己
    for i := range people {
        people[i] = i
    }

    return &UnionFindSet{
        People: people,
        N:      n,
    }
}

// Find 查找根节点
func (u *UnionFindSet) Find(x int) int {
    if u.People[x] == x {
        return x
    } else {
        // 如果他不是根节点，接着往上面找根节点，并把根节点赋给当前元素的父节点，构造二层的平铺树
        // 缩短查找距离
        u.People[x] = u.Find(u.People[x])
        return u.People[x]
    }
}

// Mix 合并两个节点到同一个联通域
func (u *UnionFindSet) Mix(x, y int) {
    fx := u.Find(x)
    fy := u.Find(y)
    // 两个人不在一个联通域，把他们两个人的Header连起来
    if fx != fy {
        u.People[fx] = fy
    }
}

程序输出如下