（19）Go实现并查集

并查集Union find，用来表示网络节点之间是否连接的集合。
这里的网络是一抽抽象的概念，不仅包括互联网，人与人形成的网络，道路之间形成的网络，迷宫网络等等。
数据存储格式如下

1）i 为节点索引， set[i] 为所属集合，若两个索引所属集合相同，表示这两节点相连
2）跟传统树结构不同的是，并查集是一种子节点指向父节点的数据结构

对并查集来说，主要支持两个动作：
1）union（p，q） // 将p，q两个节点相连
2）isConnected（p，q）  // 查询p，q是否相连，即是否属于同一个集合

下面从简单到深入，一步步优化并查集，实现5版不同的并查集，并对其性能进行对比  
//

1）第一版union find
特点：union（p，q）操作时，将set[p] = set[q]，之后遍历一遍set，
     找出所有set[i] == set[p]的索引，执行 set[i] = set[q]

// 实现
type unionSet struct {
    set  []int
}

func NewUnionSet(size int) *unionSet {
    buf := make([]int, size)
    for i := 0; i < size; i++ {
        buf[i] = i  // 初始时，所有节点均指向自己
    }
    return &unionSet{set:  buf}
}

func (set *unionSet) GetSize() int {
    return len(set.set)
}

func (set *unionSet) GetID(p int) (int, error) {
    if p < 0 || p >  len(set.set) {
        return 0, errors.New(
            "failed to get ID,index is illegal.")
    }
    return set.set[p], nil
}

func (set *unionSet) IsConnected(p, q int) (bool, error) {
    if p < 0 || p >  len(set.set) || q < 0 || q >  len(set.set) {
        return false, errors.New(
            "failed to get ID,index is illegal.")
    }
    return set.set[p] == set.set[q], nil
}

func (set *unionSet) Union(p, q int) error {
    b, err := set.IsConnected(p, q)
    if err != nil {
        return err
    }

    if !b {
        pID := set.set[p]
        qID := set.set[q]
        for k, v := range set.set {
            if v == pID {
                set.set[k] = qID
            }
        }
    }
    return nil
}
时间复杂度分析：
union()          O(n)
isConnected()    O(1)

（2）第二版union find
特点：union（p，q）操作时，找出p的根节点n，让set[q] = n 
// 实现
type unionSet struct {
    set  []int
}

func NewUnionSet(size int) *unionSet {
    buf := make([]int, size)
    for i := 0; i < size; i++ {
        buf[i] = i
    }
    return &unionSet{ set: buf}
}

func (set *unionSet) GetSize() int {
    return len(set.set)
}

func (set *unionSet) GetID(p int) (int, error) {
    if p < 0 || p > len(set.set) {
        return 0, errors.New(
            "failed to get ID,index is illegal.")
    }

    return set.getRoot(p), nil
}

// getRoot: 找出p的根节点,时间复杂度为O(h),h为树的高度
func (set *unionSet) getRoot(p int) int {
    if set.set[p] == p {
        return p
    }
    return set.getRoot(set.set[p])
}

func (set *unionSet) IsConnected(p, q int) (bool, error) {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return false, errors.New(
            "error: index is illegal.")
    }
    return set.getRoot(set.set[p]) == set.getRoot(set.set[q]), nil
}

func (set *unionSet) Union(p, q int) error {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return errors.New(
            "error: index is illegal.")
    }

    pRoot := set.getRoot(p)
    qRoot := set.getRoot(q)

    if pRoot != qRoot {
        set.set[pRoot] = qRoot
    }
    return nil
}
时间复杂度分析： // h为树的高度
union()          O(h)
isConnected()    O(h)
相比第一版，这个时间复杂度更好接受，不过在极端的情况下，
比如执行union(0,1),union(0,2)...union(0,n),这样树变成单链，
时间复杂度都为O(n)，要继续优化

（3）第三版union find
特点：加入numNode数组，numNode[ i ] 表示集合 i 中节点数量，每次执行union时，
     取出numNode的节点数量，让节点数量小的指向节点数量大的。如下图：

// 实现
type unionSet struct {
    numNode  []int // numNode[i]表示集合i中是节点数量
    set []int
}

func NewUnionSet(size int) *unionSet {
    buf1 := make([]int, size)
    for i := 0; i < size; i++ {
        buf1[i] = i
    }
    buf2 := make([]int, size)
    for i := 0; i < size; i++ {
        buf2[i] = 1  // 初始节点数量均为1
    }

    return &unionSet{
        numNode:  buf2,
        set: buf1,
    }
}

func (set *unionSet) GetSize() int {
    return len(set.set)
}

func (set *unionSet) GetID(p int) (int, error) {
    if p < 0 || p > len(set.set) {
        return 0, errors.New(
            "failed to get ID,index is illegal.")
    }
    return set.getRoot(p), nil
}

func (set *unionSet) getRoot(p int) int {
    for p != set.set[p] {
        p = set.set[p]
    }
    return p
}

func (set *unionSet) IsConnected(p, q int) (bool, error) {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return false, errors.New(
            "error: index is illegal.")
    }
    return set.getRoot(set.set[p]) == set.getRoot(set.set[q]), nil
}

func (set *unionSet) Union(p, q int) error {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return errors.New(
            "error: index is illegal.")
    }

    pRoot := set.getRoot(p)
    qRoot := set.getRoot(q)

    if pRoot != qRoot {
        if set.numNode[pRoot] < set.numNode[qRoot] {
            set.set[pRoot] = qRoot 
            set.numNode[qRoot] += set.numNode[pRoot]
        } else {
            set.set[qRoot] = pRoot
            set.numNode[pRoot] += set.numNode[qRoot]
        }
    }
    return nil
}
时间复杂度分析： // h为树的高度
union()          O(h)
isConnected()    O(h)
相比第二版，这版能有效避免树变为单链的情况，不过还能继续优化，看下图一个反面例子：

（4）第四版union find
特点：加入rank数组，rank[ i ] 表示集合高度，每次执行union(p,q)，取出p，q所在集合的高度，
      让高度低的指向高度高的。
// 实现
type unionSet struct {
    rank []int // rank[i]表示以i为根的树的高度
    set  []int
}

func NewUnionSet(size int) *unionSet {
    buf1 := make([]int, size)
    for i := 0; i < size; i++ {
        buf1[i] = i
    }
    buf2 := make([]int, size)
    for i := 0; i < size; i++ {
        buf2[i] = 1
    }

    return &unionSet{
        rank: buf2,
        set:  buf1,
    }
}

func (set *unionSet) GetSize() int {
    return len(set.set)
}

func (set *unionSet) GetID(p int) (int, error) {
    if p < 0 || p > len(set.set) {
        return 0, errors.New(
            "failed to get ID,index is illegal.")
    }

    return set.getRoot(p), nil
}

func (set *unionSet) getRoot(p int) int {
    for p != set.set[p] {
        p = set.set[p]
    }
    return p
}

func (set *unionSet) IsConnected(p, q int) (bool, error) {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return false, errors.New(
            "error: index is illegal.")
    }
    return set.getRoot(set.set[p]) == set.getRoot(set.set[q]), nil
}

func (set *unionSet) Union(p, q int) error {
    if p < 0 || p > len(set.set) || q < 0 || q > len(set.set) {
        return errors.New(
            "error: index is illegal.")
    }

    pRoot := set.getRoot(p)
    qRoot := set.getRoot(q)

    if pRoot != qRoot {
        if set.rank[pRoot] < set.rank[qRoot] {
            set.set[pRoot] = qRoot
        } else if set.rank[qRoot] < set.rank[pRoot] {
            set.set[qRoot] = pRoot
        } else { //到这步说明高度相等,谁指向谁都可以,高度要+1
            set.set[pRoot] = qRoot
            set.rank[qRoot] += 1
        }
    }
    return nil
}
时间复杂度分析： // h为树的高度
union()          O(h)
isConnected()    O(h)
从理论上讲，是比第三版更好的优化方式

先对前4版做一个性能测试对比
const count = 1000

func main() {
    nums := []int{}
    for i := 0; i < 50*count; i++ {
        nums = append(nums, rand.Intn(count))
    }
    test1(nums)
    test2(nums)
    test3(nums)
    test4(nums)
}

func test1(nums []int) {
    s := unionfind1.NewUnionSet(count)
    t := time.Now()
    for i := 1; i < 50*count; i++ {
        s.GetID(nums[i])
        s.Union(nums[i-1], nums[i])
    }
    fmt.Println("第一版时间: ", t.Sub(time.Now()))
}
func test2(nums []int) {
    s := unionfind2.NewUnionSet(count)
    t := time.Now()
    for i := 1; i < 50*count; i++ {
        s.GetID(nums[i])
        s.Union(nums[i-1], nums[i])
    }
    fmt.Println("第二版时间: ", t.Sub(time.Now()))
}
func test3(nums []int) {
    s := unionfind4.NewUnionSet(count)
    t := time.Now()
    for i := 1; i < 50*count; i++ {
        s.GetID(nums[i])
        s.Union(nums[i-1], nums[i])
    }
    fmt.Println("第三版时间: ", t.Sub(time.Now()))
}

func test4(nums []int) {
    s := unionfind5.NewUnionSet(count)
    t := time.Now()
    for i := 1; i < 50*count; i++ {
        s.GetID(nums[i])
        s.Union(nums[i-1], nums[i])
    }
    fmt.Println("第四版时间: ", t.Sub(time.Now()))
}
// 测试结果
第一版时间:  -5.101884ms
第二版时间:  -423.963439ms
第三版时间:  -1.912094ms
第四版时间:  -1.788539ms
分析：
1）加入数量优化或者高度优化的并查集性能明显优于前两版，后续要加大数量级，不再对前两版测试；
2）第二版时间更慢是因为在go的底层中，访问连续的内存地址速度要快于通过索引访问，而第二版
寻找根节点是通过索引访问的
3）第三和第四版的优化明显抵消了通过索引访问慢的劣势；
当数量级增加到1000万后，执行时间是：
第三版时间:  -1.100688529s        第三版时间:  -972.220009ms
第四版时间:  -1.066303094s        第四版时间:  -1.090987724s
两者性能差异非常小，不过第四版理论上能避免第三版最坏情况的出现，实际应用中使用第四版居多，
还能优化，加入路径压缩功能

并查集下一篇：Go--并查集2-路径压缩和性能测试
https://www.jianshu.com/p/87a723e81f5a

有bug欢迎指出

最后编辑于：2020.09.21 09:58:28

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 200,783评论 5赞 472
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,396评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 147,834评论 0赞 333
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,036评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,035评论 5赞 362
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,242评论 1赞 278
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,727评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,376评论 0赞 255
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,508评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,415评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,463评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,140评论 3赞 316
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,734评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,809评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,028评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,521评论 2赞 346
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,119评论 2赞 341

（19）Go实现并查集

推荐阅读更多精彩内容