第一种 对于quick-find的算法实现
public class UF { private int[] 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); } //quick-find算法 public int find(int p){ return id[p]; } public void union(int p,int q){ int pID=find(p); int qID=find(q); //如果pq之间已经连接,则直接返回 if (pID == qID) return; for (int i = 0; i < id.length; i++) { if(id[i] == pID) id[i] = qID; } count--; } }
在此算法中,当我们连通(union)连个对象时,先通过find方法找到他们的id[p],id[q]的值,再通过遍历整个id数组,将所有值为pID直接赋值为qID。整个算法的操作速度很快,只需要访问id[]数组一次,但无法处理大型问题,因为每一对输入unio()都需要扫描整个数组。
quick-union算法
public class UF { private int[] 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); } //quick-union算法 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--; } }
quick-union的算法运用了结构树,每个节点都能找到自己的根节点【也许是它自身】,连通对象时,算法通过find先找到p,q的根节点,最后直接将根节点的值赋值【为】q的根节点值,整个算法看似比quick-find快,但在某些输入条件下,并不快于前者,所以我们更推崇第三种。
加权quick-union算法
public class WeightedQuickUnionUF { private int[] id; private int[] sz; private int count; public WeightedQuickUnionUF(int N) { count = N; id = new int[N]; sz = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } 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--; } }
在此算法中,我们依旧利用了树的结构,但多加了一个sz数组表示 各个【根节点】所对应的分量大小,初始值都为1,在连通时,先将根节点找到,之后再比较两根节点的大小,将较小的树的根节点的值赋值【为】较大的树的根节点的值,这样可以保证较小的树总是连接到较大的树上。
第三种算法的增长级为logN