GuangchaoSun's Blog

1.5 union-find 算法

发表于  |    |   分类于   |  

动态连通性

什么叫动态连通性？

  • symmetric（对称性）: If p is connected to q, then q is connected to p.
  • transitive（传递性）: If p is connected to q and q is connected to r, then p is connected to r.
  • reflexive（自反性）: p is connected to p.

quick-find算法

public int find(int q){
    return id[q]
}
public void union(int p,int q){
    int pID = find(p);
    int qID = find(q);

    if(pID == qID) return;
    for(int i = 0;i < id.length;i++)
        if(id[i] == pID) id[i] == qID;
    count --;
}

在quick-find算法中，每次find()调用都要访问数组一次，要归并两个分量的union()操作访问数组的次数在(N+3)到(2N+1)之间。

quick-union算法

private int find(int p){
    //找出分量的名称
    while(p != id[p])
        p = id[p];
    return p;
}
public void union(int p,int q){
    //将p和q的根结点统一
    int pRoot = find(p);
    int qRoot = find(q);
    if(pRoot == qRoot) return;
    id[pRoot] = qRoot;
    count --;
}

union算法的实现（加权quick-union算法）

public class WeightedQuickUnionUF{
    private int[] id;    //父链接数组（由触点索引）
    private int[] sz;    //（由触点索引的）各个根结点所对应的分量的大小
    private int count;   //连通分量的数量
    public WeightedQuickUnionUF(int N){
        count = N;
        id = new int[N];
        for(int i = 0;i<N;i++) id[i] = i;
        sz = new int[N];
        for(int i=0;i < N;i++) sz[i] = 1;
    }

    public int count(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p) == find(q);
    }
    public int find(int p){
        //跟随链接找到根结点
        while(p != id[p]) 
            p = id[p];
        return p;
    }
    public void union(int p,int q){
        int i = find(p);
        int j = find(q);
        if (i == j) return;
        //将小树的根结点连接到大树的根结点
        if(sz[i] < sz[j]){
            id[i] = j;
            sz[j] += sz[i];
        }
        else{
            id[j] = i;
            sz[i] += sz[j];
        }
        count --;
    }
}

各种union-find算法的性能特点：

Exercise

Creative Problems

  1. Quick-union with path compression. Modify QuickUnionUF.java to include path compression, by adding a loop to find() that links every sie on the path from p to the root. Give a sequence of input pairs that causes this method to produce a path of length 4. Note: the amortized cost per operation for this algorithm is known to be logarithmic.
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
public class QuickUnionPathCompressionUF{
    	private int[] id;
    	private int count;
      	public QuickUnionPathCompressionUF(int n){
    		count = n;
    		id = new int[n];
    		for(int i = 0;i < n;i++){
    			id[i] = i;
    		}
    	}
    	public int count(){
    		return count;
    	}
    	public int find(int p){
    		int root = p;
    		while(root != id[root])
    			root = id[root];
    		while(p != root){
    			int newp = id[p];
    			id[p] = root;
    			p = newp;
    		}
    		return root;
    	}
    	public boolean connected(int p,int q){
    		return find(p) == find(q);
    	}
    	public void union(int p,int q){
    		int rootP = find(p);
    		int rootQ = find(q);
    		if(rootP == rootQ) return;
    		id[rootP] = rootQ;
    		count--;
    	}
    
    	public static void main(String[] args){
    		int n = StdIn.read();
    		QuickUnionPathCompressionUF uf = new QuickUnionPathCompressionUF(n);
    		while(!StdIn.isEmpty()){
    			int p = StdIn.readInt();
    			int q = StdIn.readInt();
    			if(uf.connected(p,q)) continue;
    			uf.union(p,q);
    			StdOut.println(p + " " + q);
    		}
    		StdOut.println(uf.count() + " components");
    	}
    }

Web Exercise