概述

并查集作为一种数据结构可以方便地合并若干个不重叠的集合,快捷地查询元素所属集合、判断两个元素是否属于同一个集合。

适用场景

并查集适用于解决整幅图的连通性问题，如：

• 网络连接判断
  如果每个pair中的两个整数分别代表一个网络节点，那么该pair就是用来表示这两个节点是需要连通的。那么为所有的pairs建立了动态连通图后，就能够尽可能少的减少布线的需要，因为已经连通的两个节点会被直接忽略掉。

• 变量名等同性(类似于指针的概念)
  在程序中，可以声明多个引用来指向同一对象，这个时候就可以通过为程序中声明的引用和实际对象建立动态连通图来判断哪些引用实际上是指向同一对象。

相关步骤

下列以网络连接判断来举例

问题建模

假设机房有n台交换机需要相互之间联通，交换机分别从0到（n-1）编码，现已有部分交换机之间两两联通（此时已联通的交换机之间没有回路），为了将机房所有交换机联通且没有回路，至少还需要多少条连接？

简单举例：若机房有9台交换机{0，1，2，3，4，5，6，7，8}，
现{{6, 8}, {0, 8}, {6, 1}, {3, 4}, {4, 5}}}是两两联通的，
则现在已联通的交换机集合为{{0，1，6，8}，{3，4，5}，{2}，{7}}，
所以还需要3条连接来将所有交换机连接起来。

初始化

以交换机的数量构建并查集，因为交换机的编号是从0开始连续递增的，
因此可以用数组来处理，若编号不连续可以考虑用hash表。

func buildUFS(num int) []int {
    result := make([]int, num)
    //先以自身为连接对象初始化
    for i := 0; i < num; i++ {
        result[i] = i
    }
    return result
}

在初始化时，每个交换机编号所对应的索引在数组中对应的值就是交换机编号本身，表示如下图所示：

初始化数组

一些概念

• 连接关系
  若交换机A和B有连接关系，则在数组中索引为A编号的值设置为B编号;
  比如说要在数组中设置{6，8}的连接关系，如图所示即可：

  
  连接关系

• 连接树
  全部相关联的连接关系组成一个连接树；
  例如{6，8}，{0，1}，{1，6}是一个连接树，是连接集合{0，1，6，8}；{3，4}, {4, 5}是另一个连接树，是连接集合{3，4，5}；
  举例中的连接树如下图所示：

  
  连接树

• 连接Root
  每个连接树中，索引与该索引在数组中的值相等的交换机即为连接Root；每颗连接树中的任意交换机都可以通过连接关系，最终获取到该连接树的连接Root；
  示例的连接Root如下图：

  
  连接Root

合并与查找

在初始化之后，要将当前已完成的两两连接按连接关系的规则合并到数组中，因此需要先判断已知的两两连接的交换机是否属于同一个连接树（分别获取两两连接的交换机所在连接树的连接Root是否相同，若相同则为同一个链接树），若不属于同一个连接树，则将两两连接的交换机所属连接树的连接Root组成连接关系
查找连接Root如下所示：

//findRoot 在并查集中查找ele所在连接树的连接Root
func findRoot(ele int, ufs []int) int {
    if ele < 0 || ele >= len(ufs) {
        return -1
    }
    root := ele
    for root != ufs[root] {
        root = ufs[root]
    }
    return root
}

合并连接如下

//union 将并查集中ele1和ele2所在的连接树合并
func union(ele1 int, ele2 int, ufs []int) {
    if ele1 < 0 || ele1 >= len(ufs) || ele2 < 0 || ele2 >= len(ufs) {
        return
    }
    root1 := findRoot(ele1, ufs)
    root2 := findRoot(ele2, ufs)

    //在并查集中两个节点不在同一个连接树中，需要进行合并
    if root1 != root2 {
        //将连接Root合并成连接关系
        ufs[root1] = root2
    }

    //路径压缩
    compress(ele1, root2, ufs)
}

经过连接合并到并查集之后，相互连接的交换机之间的连接关系程树状结构，比如{6，8}，{0，1}，{1，6}合并之后的树状结构为

未压缩连接树

在树中交换机查询连接Root的时间复杂度为logN，这将大大提升查询某个交换机属于那个连接树、并判断两个交换及是否属于同一个连接树的速度（直接遍历整个数组进行来获取的时间复杂度是logN）。

路径压缩

虽然连接合并之后，可以形成一个连接树，但是这个连接树并不稳定，有可能退化成一个链表，因此在合并连接之后需要对连接树中的连接关系进行压缩。
如图所示：

路径压缩

压缩之后所有交换机直连连接Root，使得查询的复杂度变为2，比较大的提升查询速度

路径压缩代码：

//compress 路径压缩
func compress(child int, root int, ufs []int) {
    for ufs[child] != root {
        tmp := ufs[child]
        ufs[child] = root
        child = tmp
    }
}

全部代码

编写语言为go

/*
    并查集：网络节点连接示例
    假设机房有n台交换机需要相互之间联通，交换机分别从0到（n-1）编码，
    现已有部分交换机之间两两联通（此时已联通的交换机之间没有回路），
    为了将机房所有交换机联通且没有回路，至少还需要多少条连接？

    简单举例：若机房有9台交换机{0，1，2，3，4，5，6，7，8}，
    现{{6, 8}, {0, 8}, {6, 1}, {3, 4}, {4, 5}}}是两两联通的，
    则现在已联通的交换机集合为{{0，1，6，8}，{3，4，5}，{2}，{7}}，
    所以还需要3条连接来将所有交换机连接起来。
*/
package main

import "fmt"

func main() {
    //创建并查集
    ufs := buildUFS(switchNum)
    //将已有的连接关系保存到并查集中
    for _, conn := range currentConnections {
        union(conn[0], conn[1], ufs)
    }
    //将连接分组
    groupConn := groupByUfs(ufs)
    //打印出连接各组连接
    for _, v := range groupConn {
        fmt.Println(v)
    }
}

// switchNum 机房内交换机的数量
var switchNum = 9

// currentConnections 机房内已经为两两相连的交换机
var currentConnections = [5][2]int{{6, 8}, {0, 8}, {6, 1}, {3, 4}, {4, 5}}

// buildUFS 以交换机的数量构建并查集，因为交换机的编号是从0开始连续递增的，
// 因此可以用数组来处理，若编号不连续可以考虑用hash表
func buildUFS(num int) []int {
    result := make([]int, num)
    //先以自身为连接对象初始化
    for i := 0; i < num; i++ {
        result[i] = i
    }
    return result
}

//union 将并查集中ele1和ele2所在的连接树合并
func union(ele1 int, ele2 int, ufs []int) {
    if ele1 < 0 || ele1 >= len(ufs) || ele2 < 0 || ele2 >= len(ufs) {
        return
    }
    root1 := findRoot(ele1, ufs)
    root2 := findRoot(ele2, ufs)

    //在并查集中两个节点不在同一个连接树中，需要进行合并
    if root1 != root2 {
        //将连接Root合并成连接关系
        ufs[root1] = root2
    }

    //路径压缩
    //compress(ele1, root2, ufs)
}

//findRoot 在并查集中查找ele所在连接树的连接Root
func findRoot(ele int, ufs []int) int {
    if ele < 0 || ele >= len(ufs) {
        return -1
    }
    root := ele
    for root != ufs[root] {
        root = ufs[root]
    }
    return root
}

//compress 路径压缩
func compress(child int, root int, ufs []int) {
    for ufs[child] != root {
        tmp := ufs[child]
        ufs[child] = root
        child = tmp
    }
}

func groupByUfs(ufs []int) map[int][]int {
    result := make(map[int][]int)
    for index, v := range ufs {
        root := index
        //不是root
        if index != v {
            root = findRoot(v, ufs)
        }
        if _, ok := result[root]; !ok {
            result[root] = []int{index}
        } else {
            result[root] = append(result[root], index)
        }
    }
    return result
}

参考：
https://segmentfault.com/a/1190000018089222?utm_source=tag-newest
https://blog.csdn.net/niushuai666/article/details/6662911
https://leetcode-cn.com/problems/longest-consecutive-sequence/
https://blog.csdn.net/dm_vincent/article/details/7655764