UnionFind

数据结构
数据结构

并查集

写该篇博客的初衷是由于在做天池大数据比赛中用到了并查集的相关概念，因此，想要巩固下这个知识点。

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

  • Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。

并查集用途

  • 维护无向图的连通性，支持判断两个点是否在同一个连通块内，和判断增加一条边是否会产生环
  • 用在求解最小生成树的Kruskal算法里

为了更加准确的定义这些方法，需要首先定义集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x)返回x所属集合的代表，而Union使用两个集合的代表作为参数。

代表元

用集合中的某个元素来代表这个集合，该元素称为集合的代表元。

  • 一个集合内的所有元素组织成以代表元为根的树形结构
  • 对于每一个元素，parent[x]指向在树形结构上的父亲节点。如果x是根节点，则令parent[x] = x
  • 对于查找操作，假设需要确定x所在的集合，也就是确定集合的代表元，可以沿着parent[x]不断在树形结构中向上移动，直到到达根节点。
    判断两个元素是否属于同一个集合，只需要看他们的代表元是否相同即可

并查集森林

并查集森林是一种将每一个集合以树表示的数据结构，其中每一个节点保存着它的父节点的引用，在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到树根。“联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。实现该操作的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def MakeSet(x):
    x.parent = x
def Find(x):
    if x.parent = x:
        return x
    else:
        return Find(x.parent)
def Union(x, y):
    xRoot = Find(x)
    yRoot = Find(y)
    xRoot.parent = yRoot

这是并查集森林的最基础的表示方法，这个方法并不好，因为创建的树可能会严重不平衡；可以用两种方法优化：

  • 按秩合并
    即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非他们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时秩将不会与高度相同，单元素的树的秩定义为0，当两棵秩同为r的树联合时，他们的秩为r+1。只使用这个方法将使最坏的运行时间提高至每个MakeSet、Union或Find操作O(logn)。
  • 路径压缩
    是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点，得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。

这两种方法的优势互补，同时使用二者的程序每个操作的平均时间仅为O(a(n))。因为a(n)在n十分巨大时还是小于5，因此，平均运行时间是一个极小的常数。

并查集应用

1. LintCode 178 判断图是否为树（Java实现）

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树

  • 注意事项
    你可以假设我们不会给出重复的边在边的列表当中. 无向边　[0, 1] 和 [1, 0]　是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。

  • 样例
    给出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true
    给出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.

代码如下：

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
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
    /*
     * @param n: An integer
     * @param edges: a list of undirected edges
     * @return: true if it's a valid tree, or false
     */
     
    class UnionFind {
        HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
        UnionFind(int n) {
            for (int i=0; i < n; i++) {
                father.put(i, i);
            }
        }
        
        int compressed_find(int x) {
            int parent = father.get(x);
            while(parent != father.get(parent)) {
                parent = father.get(parent);
            }
            int temp = -1;
            int fa = father.get(x);
            while (fa != father.get(fa)) {
                temp = father.get(fa);
                father.put(fa, parent);
                fa = temp;
            }
            return parent;
        }
        
        void union(int x, int y) {
            int fa_x = compressed_find(x);
            int fa_y = compressed_find(y);
            if (fa_x != fa_y)
                father.put(fa_x, fa_y);
        }
    } 
     
    public boolean validTree(int n, int[][] edges) {
        // write your code here
        if (n - 1 != edges.length) {
            return false;
        }
        
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < edges.length; i++) {
            if (uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])) {
                return false;
            }
            uf.union(edges[i][0], edges[i][1]);
        }
        return true;
    }
}

2. 天池比赛中用于图之间任意两个节点是否有连接（Python实现）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class UnionFind(object):
    def __init__(self, groups):
        self.groups = groups # 外部传入的相连接的点
        self.items = [] # 所有的元素
        for group in groups:
            self.items += list(group)
        self.items = set(self.items)
        self.parent = {} # 父亲节点
        for item in self.items:
            self.parent[item] = item
        self.create_tree()
    def findroot(self, r):
        """
        查找根节点
        """
        if r == self.parent[r]:
            return r
        else:
            # 路径压缩
            self.parent[r] = self.findroot(self.parent[r])
            return self.parent[r]
    def union(self, p, q):
        """
        合并p和q两个节点
        """
        p_root = self.findroot(p)
        q_root = self.findroot(q)
        if p_root == q_root:
            return
        # 将父节点指向另一个节点
        self.parent[p_root] = q_root
        return
    def create_tree(self):
        """
        根据groups来构造树结构
        """
        for group in self.groups:
            if len(group) < 2:
                continue
            for i in range(len(group) - 1):
                if self.findroot(group[i]) != self.findroot(group[i + 1]):
                    self.union(group[i], group[i + 1])
    def is_connected(self, p, q):
        """
        判断两个节点是否连接
        """
        if p not in self.items or q not in self.items:
            return False
        return self.findroot(p) == self.findroot(q)
    def add_groups(self, groups):
        """
        增加连接
        """
        self.groups = self.groups + groups
        for group in groups:
            for item in group:
                if item in self.items:
                    continue
                self.items = list(self.items)
                self.items.append(item)
                self.parent[item] = item
        self.items = set(self.items)
        self.create_tree()
    def print_trees(self):
        """
        打印出相连接的树结构
        """
        rs = {}
        for item in self.items:
            root = self.findroot(item)
            rs.setdefault(root, [])
            rs[root].append(item)
        for key in rs:
            print (rs[key])
            print ('*************************')
    def get_items(self):
        """
        获取所有的元素
        """
        return self.items
if __name__ == '__main__':
    # 测试功能
    groups = [((1,1), (1,2)), ((3,4), (3,3)), ((1,1), (0,1))]
    u = UnionFind(groups)
    u.print_trees()
    u.add_groups([((3,4), (3,5))])
    print ('after adding')
    u.print_trees()
    print (u.is_connected((1,1), (3,4)))
    print(u.is_connected((1, 2), (0, 1)))
Compartir Comentarios