《算法》-1.5-并查集算法

并查集(union-find)算法

并查集算法真的是简单却又非常实用的一种算法，要想理解这个算法可以用一个非常生动的例子说明，叫解密犯罪团伙，这是从《啊哈算法》看到的，讲解的非常生动形象。在一堆数量为n的犯人里，如果n1和n2是团伙，n2又和n3是一伙，诸如此类的线索还有很多，问你，这n个人里有多少个犯罪团伙？其实还有个例子可以非常清楚到位的概括这个模型，那就是平面上有n个点，给定一条边既可以将两个点联通起来，现在有大量的这样的边，问最后有多少个连通子图？

为了计算无向图中的联通子图问题，并查集算法就能很有效的完成这个任务，还可以查询到任意两个顶点是否连通，下面是实现的代码；

首先要明白并查集能干什么？以下是并查集的功能，或者是我们使用并查集的需求所在；

• 从一堆连接任意两个顶点的边信息中创建并查集
• 可以查询到任意两个顶点是否连通？
• 对于指定边能够将该边的两个顶点连通起来让他们属于同一个子图
• 能够找到某一个顶点所在子图的根在哪儿
• 计算一个图中的连通分量有多少个？

union find算法实现

下面给出并查集算法的简易api如下

public class UF UF(int n); // 创建包含n个顶点的并查集 void union(int p, int q); // 连接顶点p和q int find(int p); // 查找p所在分量的标识符 boolean connect(int p, int q); // 判别两个顶点是否连通 int count(); //返回图中总共的连通分量数目

下面是测试实例和具体代码实现；

package PAT; import java.util.Scanner; public class UF { 
     private int count; private int[] id; public UF(int n) { id = new int[n]; for(int i=0; i 
   
     public 
    static 
    void 
    main(String[] args) { Scanner s = 
    new Scanner(System.in); 
    int n = s.nextInt(); UF test = 
    new UF(n); 
    int m = s.nextInt(); 
    for( 
    int i= 
    0; i 
    
      int p = s.nextInt(); 
     int q = s.nextInt(); 
     if(test.connected(p, q)) 
     continue; test.union(p ,q); } } 
     private 
     void 
     union( 
     int p, 
     int q) { 
     int r1 = find(p); 
     int r2 = find(q); 
     if(r1 == r2) 
     return; id[r1] = r2; count --; } 
     private 
     boolean 
     connected( 
     int p, 
     int q) { 
     return find(p) == find(q); } 
     private 
     int 
     find( 
     int p) { 
     while(p != id[p]) p = id[p]; 
     return p; } } 
     
   

下面是测试数据：

10 11 4 3 3 8 6 5 9 4 2 1 8 9 5 0 7 2 6 1 1 0 6 7

测试结果如下：

分量有2个 true

思考？

实际上上面的union-find算法在id[]数组里创建了一棵树，这棵树有根节点，有叶节点，有中间节点，还有多颗树，这里面核心就是快速查找到某一个顶点的根节点是哪个节点，无论是在查的过程，或者是将要并的过程中，核心都在find函数中，那么有什么方法能使我的找根节点的时候更快么？这句话翻译一下，就是怎么降低这颗树的高度呢？只要树的高度降低了，我就可以很快的查到两个顶点的根节点是否是同一个，这将大大提高并查集算法用于查询的效率，所以为了做到这一点，便有了加权以后的并查集算法，她的核心思想不在改变find上，而在于union方法里，上述的union方法中，默认是将p的根节点变成q的根节点，也即将p所在的子树，依附到q所在的树上去，这样做是不加思考的，因为很可能导致q所在树越来越长，变成一颗极为不平衡的树，为了解决这个问题，我们只需要在union方法中，通过权重进行判别，如果q树比p树更高，那么就让p树依附到q树去，反之就让q树依附到p树去，每次都保证是小树依附到大树上去，这样构建的树就为较为平衡的树，这样对于任意节点，在搜索根节点过程中，效率将大大提高，并查集算法得到优化；

下面附上具体实现的代码：

package PAT; import java.util.Arrays; import java.util.Scanner; public class UF { 
      private int count; private int[] id, size; public UF(int n) { id = new int[n]; size = new int[n]; for(int i=0; i 
    
      1; } count = n; } 
     public 
     static 
     void 
     main(String[] args) { Scanner s = 
     new Scanner(System.in); 
     int n = s.nextInt(); UF test = 
     new UF(n); 
     int m = s.nextInt(); 
     for( 
     int i= 
     0; i 
     
       int p = s.nextInt(); 
      int q = s.nextInt(); 
      if(test.connected(p, q)) 
      continue; test.union(p ,q); } System.out.println(Arrays.toString(test.id)); System.out.println( 
      "分量有" + test.count + 
      "个"); System.out.println(test.connected( 
      2, 
      5)); } 
      private 
      void 
      union( 
      int p, 
      int q) { 
      int r1 = find(p); 
      int r2 = find(q); 
      if(r1 == r2) 
      return; 
      if(size[r1] < size[r2]) { id[r1] = r2; size[r2] += size[r1]; } 
      else { id[r2] = r1; size[r1] += size[r2]; } count --; } 
      private 
      boolean 
      connected( 
      int p, 
      int q) { 
      return find(p) == find(q); } 
      private 
      int 
      find( 
      int p) { 
      while(p != id[p]) p = id[p]; 
      return p; } } 
      
    

测试数据

8 7 0 1 1 2 3 4 3 5 3 6 3 7 2 7

输出结果：

[3, 0, 0, 3, 3, 3, 3, 3] 分量有1个 true

在我看来，这样的平衡调整，可以更好！为什么不能是下图这样呢?

而想要做到这样的优化，并非难事，只要将union函数改成下述即可：

 private void union(int p, int q) { int r1 = find(p); int r2 = find(q); if(r1 == r2) return; if(size[r1] < size[r2]) { id[r1] = r2; if(size[r1] + 1 > size[r2]) size[r2] += size[r1]; } else { id[r2] = r1; if(size[r2] + 1 > size[r1]) size[r1] = size[r2] + 1; } count --; }

多加一个判定即可，笔者认为这样构建的树就比上一个小树依附大树的效果要好的多，因为这里size数组里寸的不是该树的所有顶点个数，而是实实在在的最大高度，这是最关键的信息。不是让一个瘦子去依附胖子，而是让一个小个去依附高个儿。

测试数据如下：

8 7 0 1 1 2 3 4 3 5 3 6 3 7 2 7

输出结果：

[0, 0, 0, 0, 3, 3, 3, 3] 分量有1个 true

并查集算法经常出现在很多图的问题中，不过常常是作为解题的一小步，不过这一小步也是非常的重要。