并查集是一种数据结构,在合并不相交的集合,用来判断一个图中是否有环这种问题时,具有很高的性能。

并查集

并查集的主要操作就是为一个集合中的元素找到一个代表(根节点)。并查集的基本操作是合并两个集合,当拿到两个节点,第一步需要找到各自节点的根,然后选择一个节点作为新的代表,那么就完成了两个集合的合并。

并查集实现

并查集可以使用一个数组来表示,数组表示图上的节点,下标表示节点的编号,数组的值表示该下标的父节点是哪一个。例如A[0] = 1 表示节点0的父节点是节点1.

并查集的实现过程主要分为两步,一步是实现节点的根的查找,另一步是实现两个集合的合并,这里包含了节点的路径压缩。

下面实现find_root算法:

1
2
3
4
5
6
7
8
joint = 10
parent = [-1]*10

def find_root(parent,x):
x_root = x
while parent[x_root] != -1:
x_root = parent[x_root]
return x_root

上面代码说明当x不是根节点时,循环继续往上找,当x时根节点时则返回。

下面是union的算法:

1
2
3
4
5
6
7
8
9
def union_joint(parent,x,y):
x = find_root(parent,x)
y = find_root(parent,y)
if x == y:
print('circle')
return 0
else:
parent[x] = y
return 1

上诉代码如果返回的结果是0的话则说明存在一个环,否则不存在环。

存在一种极端的情况,即每次union合成的集合它形成了一个很长的链,每次寻找一个节点的根需要遍历一下整个节点,复杂度太高,下面在union中引入路径压缩的思想,即引入另一个数组rank,表明当前节点的位置,当进行union的时候,rank小的数连接到rank大的树底下,当两个rank相同的时候,可以随意连接,但是连接之后作为父节点的rank需要加1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
rank = [0]*joint
def union(parent,x,y,rank):
x = find_root(parent,x)
y = find_root(parent,y)
if x == y:
print('circle')
return 0
else:
if rank[x] > rank[y]:
parent[y] = x
elif rank[x] < rank[y]:
parent[x] = y
else:
parent[x] = y
rank[y] += 1

在判断一个图是否存在环的时候,依次遍历图的所有边,如果union返回的结果是0的话,表明有环。

下面是一道lettcode的题目,思路就是用并查集来求解:

547.Friend Circles

思路是将朋友的关系用边来表示,最后看parent数组中有多少根节点(等于-1)。

解法代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
edge = []
if M == [] or M[0] == []:
return 0
for i in range(len(M)):
for j in range(len(M[0])):
if i <= j:
break
if M[i][j] == 1:
edge.append([i,j])

parent = [-1]*len(M)
rank = [0]*len(M)

def find_root(parent,x):
x_root = x
while parent[x_root] != -1:
x_root = parent[x_root]
return x_root
def union_joint(parent,x,y,rank):
x = find_root(parent,x)
y = find_root(parent,y)
if x != y:
if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x
else:
parent[x] = y
rank[y] += 1

for e in edge:
union_joint(parent,e[0],e[1],rank)
ans = 0
for i in parent:
if i == -1:
ans += 1
return ans