chapter15-unionFindSets-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 603 | Reading time ≈ 3

chapter15-unionFindSets-algorithm

[TOC]

并查集算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 并查集存储是一数组进行举例说明，限制：值不能够大于下标，切必须为数字
# 对于不同的场景来说，以及不同的数据类型，你都可以利用字典这种数据结构进行范围
# 数据结构是死的，思想是活的

# 父类
class UF:
    def __init__(self, N):
        self.id = [i for i in range(N)]

    # 查找元素的父亲是谁
    def find(self, p):
        pass

    # 判断两个元素的父亲是否相等
    def connected(self, p, q):
        return self.find(p) == self.find(q)

    # 合并两个元素(也就是构建的过程)
    def union(self, p, q):
        pass
1. Quick Find
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
class QuickFindUF(UF):
    def __init__(self, N):
        super().__init__(N)

    def find(self, p):
        return self.id[p]

    def union(self, p, q):
        pid = self.find(p)
        qid = self.find(q)

        if pid == qid:
            return
        for i in range(len(self.id)):
            if self.id[i] == pid:
                self.id[i] = qid
                
print('***********QuickFindUF************')
s = QuickFindUF(5)
print(s.find(1))
s.union(2, 3)
s.union(3, 4)
print(s.id)
s.union(0, 2)
print(s.find(1))
print(s.connected(0, 2))
print(s.id)
2. Quick Union
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
class QuickUnionUF(UF):
    def __init__(self,N):
        super(QuickUnionUF, self).__init__(N)

    def find(self, p):
        while p != self.id[p]:
            p = self.id[p]
        return p

    def union(self, p, q):
        pRoot = self.find(p)
        qRoot = self.find(q)

        if pRoot != qRoot:
            self.id[pRoot] = self.id[qRoot]

print('***********QuickUnionUF************')
s = QuickUnionUF(5)
print(s.find(1))
s.union(2, 3)
s.union(3, 4)
print(s.id)
s.union(0, 2)
print(s.find(1))
print(s.connected(0, 2))
print(s.id)
3. 加权 Quick Union
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 WeightedQuickUnionUF(UF):
    def __init__(self, N):
        super(WeightedQuickUnionUF, self).__init__(N)
        self.sz = [1 for i in range(N)]


    # def find(self, p):
    #     while p != self.id[p]:
    #         p = self.id[p]
    #     return p

    def find(self, p):
        while p != self.id[p]:
            # 直接更改当前值为根节点(第一种并查集的find的结果，接近)
            self.id[p] = self.id[self.id[p]]
            p = self.id[p]
        return p

    # 防止建为一个很高的数
    def union(self, p, q):

        i = self.find(p)
        j = self.find(q)

        if i == j: return

        if self.sz[i] > self.sz[j]:
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]

print('***********WeightedQuickUnionUF************')
s = QuickUnionUF(5)
print(s.find(1))
s.union(2, 3)
s.union(3, 4)
print(s.id)
s.union(0, 2)
print(s.find(1))
print(s.connected(0, 2))
print(s.id)
4. 路径压缩的加权 Quick Union
1
2
3
4
5
6
7
8
9
# 在检查节点的同时将它们直接链接到根节点，只需要在 find 中添加一个循环即可。 如上find1

# 比较
'''
算法	union	find
Quick Find	N	1
Quick Union	树高	树高
加权 Quick Union	logN	logN
路径压缩的加权 Quick Union	非常接近 1	非常接近 1