一、什么是并查集
并查集是图论中的一种算法
集就是集合，因此可以看出并查集与集合操作有关
并查集内有两个重要的操作：合并(union)，查询(find)
合并操作是用来将不同的集合合并为一个集合，查询操作用来查询某个元素所属的集合
二、举个栗子
1. 栗子
假设现在有六个元素，代号分别为1、2、3、4、5、6
他们的集合关系如下，{1, 2}, {1, 5}, {3, 4}, {6, 2}，在同一花括号内表示处在同一集合中
问元素[1, 3]，元素[2, 5]是否在同一集合内
思路：根据提供的集合关系，将同一集合内的元素连在一起，每个集合选取一个根节点作为集合的代表，若两个元素所处集合的根节点相同，则表示这两个元素在同一集合内
逐步建立他们的集合关系如下
初始时，每个元素都是一个集合，他们的根节点都是自己，例如：parent[1] = 1
合并元素1和元素2，此时根节点分别为1，2，任意选取元素1作为合并后集合的根节点
将元素5与元素1合并到一个集合中，根节点分别为1，5，任意选取元素5作为合并后集合的根节点
合并元素3和元素4，根节点分别为3，4，任意选取元素3作为合并后集合的根节点
合并元素2和元素6，根节点分别为5，6，任意选取元素6作为合并后集合的根节点
集合关系就建立完毕啦！
这时候开始判断元素所属集合是否相同
[1, 3]
元素1所处集合的根节点是6，元素3所处集合的根节点是3，因此他们属于不同的集合
[2, 5]
元素5所处集合的根节点是6，元素2所处集合的根节点也是6，因此他们在同一集合内
2. 检测环的存在
并查集还可以用来判断是否有环的存在
例如，我们在原有集合的基础上，再添加一条关联关系{1, 6}
元素1所在集合的根节点是6，元素6所在集合的根节点也是6，他们在同一集合中，因此若继续添加关联关系则会导致环的产生
3. 代码实现
直接用golang实现
// 初始化
func initArray(parent []int) {
for i := 0; i < len(parent); i++ {
parent[i] = -1
}
}
// 查找根节点
func find(node int, parent []int) int {
if parent[node] == -1 {
return node
}
return find(parent[node], parent)
}
// 合并集合
func union(x, y int, parent) bool {
xRoot := find(x, parent)
yRoot := find(y, parent)
if xRoot == yRoot { // 根节点相同表示存在环
return false
}
parent[xRoot] = yRoot
return true
}
func TestDisjointSet(t *testing.T) {
elementCount, relationCount, questionCount := 6, 4, 2
var relations = [][]int{
{1, 2}, {1, 5}, {3, 4}, {6, 2},
}
var P = [][]int{
{1, 3}, {2, 5},
}
// 1. 初始化
parent := make([]int, elementCount+1)
initArray(parent)
// 2. 合并集合
for i := 0; i < relationCount; i++ {
union(relations[i][0], relations[i][1], parent)
}
// 3. 判断是否为同一集合
for i := 0; i < questionCount; i++ {
aRoot := find(P[i][0], parent)
bRoot := find(P[i][1], parent)
if aRoot == bRoot {
t.Log(true)
continue
}
t.Log(false)
}
}
执行结果
三、路径压缩
1. 路径优化
上述的步骤中，左侧的集合极端情况下需要遍历全链表，因此需要考虑用路径压缩做优化
还以上面的元素举例，初始状态仍是六个集合，要建立的关联关系如下：{1, 2}, {1, 5}, {3, 4}, {6, 2}
最初为每个集合赋予基础深度rank为0（这里初始赋值为几并不重要，它只用来做大小比较，只要每个元素的初始值相同即可）
整合元素1和元素2，根节点分别为1，2，此时他们的集合内元素的数量相等，因此可以随意指定一个根节点，这里最终选定的根节点的rank要加一，表示树深度的增加
整合元素1和元素5，根节点分别为1，5，而rank[1] > rank[5]，因此选择元素1作为最终的根节点，保证树的深度尽可能的小，这也是路径压缩的目的，这里树的深度没有增加，因此rank[1]不用自增
整合元素3和元素4，根节点分别为3，4，rank[3] == rank[4]，因此可以任意选择一个根节点，且rank[root]++
整合元素6和元素2，根节点分别为1，6，rank[1] > rank[6]，选择让元素1作为最终的根节点
这里最终生成树的层级比上面的层级更小，遍历起来也更快，这就是路径压缩，让生成树的深度尽可能的小，减少需要遍历的节点
路径压缩的基本思想就是将深度更小的树挂载到深度更大的树上，保证最终的树深度尽可能小
2. 代码实现
// 初始化
func initArray(parent, rank []int) {
for i := 0; i < len(parent); i++ {
parent[i] = -1
rank[i] = 0
}
}
// 查找根节点
func find(node int, parent []int) int {
if parent[node] == -1 {
return node
}
return find(parent[node], parent)
}
// 合并集合
func union(x, y int, parent, rank []int) bool {
xRoot := find(x, parent)
yRoot := find(y, parent)
if xRoot == yRoot {
return false
}
if rank[xRoot] > rank[yRoot] {
parent[yRoot] = xRoot
} else if rank[xRoot] < rank[yRoot] {
parent[xRoot] = yRoot
} else {
parent[xRoot] = yRoot // 这里随便选哪个节点都可以
rank[yRoot]++
}
return true
}
func TestDisjointSet(t *testing.T) {
elementCount, relationCount, questionCount := 6, 4, 2
var relations = [][]int{
{1, 2}, {1, 5}, {3, 4}, {6, 2},
}
var P = [][]int{
{1, 3}, {2, 5},
}
// 1. 初始化
parent := make([]int, elementCount+1)
rank := make([]int, elementCount+1)
initArray(parent, rank)
// 2. 合并集合
for i := 0; i < relationCount; i++ {
union(relations[i][0], relations[i][1], parent, rank)
}
// 3. 判断是否为同一集合
for i := 0; i < questionCount; i++ {
aRoot := find(P[i][0], parent)
bRoot := find(P[i][1], parent)
if aRoot == bRoot {
t.Log(true)
continue
}
t.Log(false)
}
}
执行结果