算法笔记－案例研究：union-find(并查集)算法

设计API

``````//public class UF
//             UF(int N)                                  初始化整个集合
//        void union(int p, int q)                        在p,q之间添加一条连接
//         int find(int p)                                p所在的链的标识符
//     boolean connected(int p, int q)                    如果p和q存在于同一条链之中则返回true
//         int count()                                    统计集合中链的数量
//
``````

最初版本的实现－quick find
``````import java.util.Scanner;
public class UF {
private int[] id;     //分量id,以触点作为索引
private int count;    //分量数量

public UF(int N){
count = N;
id = new int[N];
for (int i = 0;i < N;i++){
id[i] = i;
}
}

public int count(){
return count;
}

public boolean connected(int p, int q){
return find(p) == find(q);
}
public int find(int p){
return id[p];
}

public void union(int p , int q){
//将p和q所属的分量归并(连接两条链)
int pID = find(p);
int qID = find(q);

//如果p和q已经在相同的分量当中则不需要采取任何行动
if (pID==qID) return;

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

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();

UF uf = new UF(N);

while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}

System.out.println(uf.count + "components");

}

}
``````

第一次改进后的实现－quick union
``````import java.util.Scanner;
public class UF {
private int[] id;     //分量id,以触电作为索引
private int count;    //分量数量

public UF(int N){
count = N;
id = new int[N];
for (int i = 0;i < N;i++){
id[i] = i;
}
}

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 pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;

id[pRoot] = qRoot;
count--;
}

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();

UF uf = new UF(N);

while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}

System.out.println(uf.count + "components");

}

}

``````
qucik-union_算法(第四版)原书中的图

第二次改进后的实现－加权quick-union算法

``````import java.util.Scanner;
public class UF {
private int[] id;     //分量id,以触点作为索引
private int[] size;   //由触电索引的各个节点所对应的分量的大小
private int count;    //分量数量

public UF(int N){
count = N;
id = new int[N];
for (int i = 0;i < N;i++){
id[i] = i;
}
size = new int[N];
for (int i = 0;i < N;i++){
size[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 pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;

if (size[pRoot] < size[qRoot]){
id[pRoot] = id[qRoot];
size[qRoot] += size[pRoot];
}else {
id[qRoot] = id[pRoot];
size[pRoot] += size[qRoot];
}
count--;
}

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();

UF uf = new UF(N);

while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}

System.out.println(uf.count + "components");

}

}

``````

最优算法－路径压缩的加权quick-union算法

``````public int find(int p){
int temp = p;
while (p != id[p]) p = id[p];
id[temp] = id[p];
return p;
}
``````

资源以及参考

http://algs4.cs.princeton.edu/15uf/largeUF.txt

cd到.java文件所在文件夹，执行一下命令，如果.java文件中含有包名，注意将其删除
% javac UF.java
% java UF < largeUF.txt