union-find算法的研究

union-find算法研究

三种union-find算法的性能特点

算法构造函数union()find()quick-find算法NN1quick-union算法N树的高度树的高度加权quick-union算法NlgNlgN

1.quick-find

public int find(int p) {return id[p];} public void union(int p, int q) {//将p和q归并到相同的分量中 int pID = find(p); int pID = find(q); //如果p和q已经在相同的分量中则不需要采取任何行动 if(pID == qID) return; //将p的分量重命名为q的名称 for(int i = 0; i < id.length; i++) if(id[i] == pID) id[i] = qID; count--; }

2. quick-union算法

private int find(int p) {//找出分量的名称 while(p != id[] 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--; }

3.加权quick-union算法

public class WeightQuickUnionUF { 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 = 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--; } }

总结

quick-find算法是平方级别的，如果N很大，成本很大，因此算法不可行quick-union算法的成本主要依赖输入的特点，最好的情况，它的运行时间是线性级别的，最坏的情况是平方级别的，所以该算法仍然存在问题，我们不能保证所有情况它都比quick-find算法快的的多。加权quick-union算法能够保证对数级别的性能，因此它的效率最高。