快速查找（贪心算法）
目的：通过并查集解决动态连通性问题
定义： 在一个N个元素的数组中，当且仅当 p、q的id相等时，p和q是连通的。
接口
/**
* 判断两个元素是否连通： 比对id值是否相等即可
*/
public boolean connected(int p, int q)；
/**
* 连通p、q
* 将所有与p相同id的元素的id值都变更为q的id值
*/
public void union(int p, int q)；
算法实现
/**
* 动态联通问题之快速查找（贪心算法）
*
* 定义: 在一个N个元素的数组中，当且仅当 p、q的id相等时，p和q是连通的。
*
*/
public class QuickFindUF {
private int[] id ;
public QuickFindUF(int n) {
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
/**
* 判断p、q是否连通
* @param p
* @param q
* @return
*/
public boolean connected(int p, int q) {
return id[p] == id[q];
}
/**
* 连通p、q
* 将所有与 p 相同 id 的元素的 id 值 都变更为 q 的 id 值
* @param p
* @param q
*/
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid ) id[i] = qid;
}
}
public static void main(String[] args) {
QuickFindUF quickFindUF = new QuickFindUF(10);
quickFindUF.union(0,5);
quickFindUF.union(5,6);
quickFindUF.union(1,2);
quickFindUF.union(2,7);
quickFindUF.union(8,3);
quickFindUF.union(3,4);
quickFindUF.union(4,9);
System.out.println(quickFindUF.connected(1,3));
System.out.println(quickFindUF.connected(8,9));
}
}
算法效率：
image
总结
查询速度为1（即直接比对元素的id值即可），但进行N次连通操作的时间复杂度为指数级增长，速度太慢。
