Golang实现并查集

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

模拟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
    }
}

程序输出如下


图片.png

图片.png

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:FredricZhu

查看原文:Golang实现并查集

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

179 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传