加权快速联合（Weighted Quick Union）算法原理及实现（Java）

大家好，欢迎来到IT知识分享网。

public int parent(int p); // 返回节点p的parent节点 public boolean isConnected(int p, int q); // 判断节点p和q是否属于同一个集合 public void connect(int p, int q); // 连接节点p和节点q public int find(int p); // 返回节点p的root节点 

底层实现
  利用数组存放每个节点的parent节点，其中每个集合的root节点以负数的形式存放本集合的节点数量值。当连接两个集合中的元素时，如connect(8, 3)，以节点数较多的集合的root节点作为新集合的root节点（所以被称为加权快速联合）。

  connect(8, 3)

java代码
  WQU.java

public class WQU { 
     private int[] nums; private int size; WQU() { 
     this.size = 10; this.nums = new int[size]; for (int i = 0; i < size; i++) { 
     this.nums[i] = -1; } } public int parent(int p) { 
     /* the parent of p */ return this.nums[p]; } public boolean isConnected(int p, int q) { 
     /* check if p and q in the same group */ return find(p) == find(q); } public void connect(int p, int q) { 
     /* connect p and q */ if (!isConnected(p, q)) { 
     int rootP = find(p); int rootQ = find(q); if (nums[rootP] < nums[rootQ]) { 
     merge(rootQ, rootP); } else { 
     merge(rootP, rootQ); } } } private void merge(int p, int q) { 
     nums[q] += nums[p]; nums[p] = q; } public int find(int p) { 
     /* the root of p */ int origin = p; while (parent(p) >= 0) { 
     p = parent(p); nums[origin] = p; } return p; } public void printAllNum() { 
     for (int i = 0; i < size; i++) { 
     System.out.print(nums[i] + " "); } System.out.print("\n"); } } 

  Test.java

public class Test { 
     / * 对WQU的功能进行测试 */ public static void main(String[] args) { 
     WQU t = new WQU(); t.connect(1, 0); t.connect(2, 0); t.connect(3, 0); t.connect(4, 0); t.connect(5, 0); t.connect(7, 6); t.connect(9, 8); t.connect(8, 6); t.printAllNum(); // t.connect(8, 3); t.connect(9, 3); // connect(9, 3) 检验find的优化效果 t.printAllNum(); t.find(8); // 再次检验find的优化 t.printAllNum(); } } 

优化
  在每次进行find(int p)后，如果节点p没有直接和root相连，则将其和root直连（修改数组中对应位置的值即可）。这样可以优化find的效率，这种算法被称为带路径压缩的加权快速联合。