并查集 Disjoint Set

Posted on | In
Words count in article: 1.2k | Reading time ≈ 4

并查集(Disjoint Set)

互不相交的数据集合。用一个代表元素来识别每个集合，这个元素属于这个集合。基本操作如下：
Make-Set：建立一个新的单元素集合
Find：判断元素在哪个集合中。可用于判断两个元素是都属于同一集合。
Union：把一个集合中的元素并入另一个集合中。
该数据结构可用于确定无向图的连通分量：对每个顶点make-set，遍历每一条边对每条边的两顶点的所在set进行union，最终得到的set的集合就是无向图的连通分量。

并查集的链表表示

每个集合的对象包含head属性和tail属性，head属性指向第一个对象，tail属性指向最后一个对象。链表中每个对象包含一个集合成员、一个next指向下一个对象，一个head回到集合对象。此时make-set、find操作时间复杂度为$O(1)$，union的时间复杂第为$O(n)$，其中n为被合并的集合大小，union操作将改变这n个元素的head指针。
一种加权合并启发式策略 weighted-union heuristic：每次都是将较小的链合并到较长的链中。
一个具有m个make-set、union、find操作的序列需要消耗$O(m+nlgn)$的时间（n：make-set的个数）。：总共至多执行n-1次union操作，对某个元素x，x的指针每次被更新，说明x一定在一个较小的集合中，x被更新$[lgk]$次说明集合一定至少有k个成员了，因此每个元素所在集合最多被合并$[lgn]$次。总共花在union操作的时间为$O(nlgn)$。

并查集的数组表示

Make-Set：对n个元素创建一个长度为n的数组P，每个数组元素都是-1。$O(1)$
Find：查找这个元素x作为index存储的数值P(x)，如果是-1则返回自己，如果不是则返回Find(P(x))。$O(n)$
Union：将被合并的集合的代表元素的对应数值改为合并的集合的代表元素。$O(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
class disjoint_set{
 int[] parent;
 disjoint_set(int n){
 	this.parent = new int[n];
 	for(int i = 0; i < n; i ++) {
 		this.parent[i] = -1;
 	}
 }
 int find_set(int x) {
 	if(this.parent[x] < 0) return x;
 	return find_set(this.parent[x]);
 }
    void union(int x1, int x2) {
        int s1 = find_set(x1);
  int s2 = find_set(x2);
  if(s1 == s2) return;
        //union by rank, using size as rank
  if(this.parent[s1] <= this.parent[s2]) {
  	//the set of x1 have more elements
  	this.parent[s1] += this.parent[s2];
  	this.parent[s2] = s1;
  }
  else {
  	this.parent[s2] += this.parent[s1];
  	this.parent[s1] = s2;
  }
 }
}

//main function
public class Main {
    public static void main(String[] args) {
       disjoint_set ds = new disjoint_set(5);
       System.out.println(ds.find_set(3)); //output:3
       ds.union(1, 2);
       ds.union(1, 3);
       System.out.println(ds.find_set(1)); //output:1
       System.out.println(ds.find_set(2)); //output:1
       System.out.println(ds.find_set(3)); //output:1
    }
}

并查集森林 disjointed-set forest 与启发式策略

每个成员仅指向其父节点，每棵树的根就是集合的代表，根节点的父节点就是根节点本身。
Find-Set操作即沿着指向父节点的指针找到树根。这一通向根节点的简单路径上所访问的结点构成了查找路径(find path)。
Union操作即将一棵树的根节点指向另一棵树的根节点。
一个包含n-1个union操作的序列可以构造出一颗恰好含有n个结点的并查集森林。

按秩合并 Union by Rank

使具有较少节点的树的根指向具有较多结点的树的根。对于每个结点，维护一个秩(rank)用来表示该节点高度的一个上界。在union操作中可以让具有较小秩的根指向具有较大秩的根。

路径压缩 Path Expression

指针策略可以使查找路径中每个结点直接指向根。路径压缩并不改变任何结点的秩。

无向图中探测环

对每个顶点make-set，遍历每条边，找到当前边的两个顶点所在的集合，如果不同，则对这两个集合进行union操作；如果相同，则图中出现环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class graph{
 disjoint_set ds;
 graph(int v){
 	this.ds = new disjoint_set(v);
 }
 void addEdge(int x1, int x2) {
 	System.out.println("add edge: " + String.valueOf(x1) + " " + String.valueOf(x2));
 	int s1 = this.ds.find_set(x1);
  int s2 = this.ds.find_set(x2);
  if(s1 == s2) System.out.println("there is a circle");
  this.ds.union(x1, x2);
 }
}

//main function
public class Main {
    public static void main(String[] args) {
     graph g = new graph(3);
     g.addEdge(0, 1); //add edge: 0 1
     g.addEdge(1, 2); //add edge: 1 2
     g.addEdge(0, 2); //add edge: 0 2 there is a circle
    }
}