1、问题描述

动态连通性问题。给定一组数，为0-N-1,然后给定一组整数对，每个整数对表明这两个整数是相连的，在接受整数对是，如果二者不相连，则输出该整数对。2与3相连，1与2相连，则1与3相连。

  1. 需要实现一个类，四个函数
  3.     UF(int N);//初始化该类，有N个整数，0-N-1
  4.    void union(int q , int p);//在p和q上建立一条连接
  5.    int find(int p);//返回p所在的连通分量标识
  6.   boolean connected(int p . int q);//如果p和q存在于同一个分量中则返回true
  7.   int count();//返回连通分量的个数

2、quick-find算法

保留一个数组，记录该整数对应的连通分量标识，初始时连通分量为自身，连接两个数时，如果两个数的连通分量不一样，需要把两个连通分量的所有数的标识统一。

  1. package union_find;
  3. import java.util.Queue;
  5. /**
  6.  * @author zwlstart
  7.  * @create 2020-12-19 20:56
  8.  */
  9. public class QuickFind {
  10.     //记录每个数的连通分量的标识
  11.     int[] id;
  12.     //记录连通分量的个数
  13.     int count;
  15.     public QuickFind() {
  17.     }
  19.     public QuickFind(int n) {
  20.         id = new int[n];
  21.         //连通分量个数初始化为n
  22.         count = n;
  23.         //初始化每个整数的连通分量标识为自己
  24.         for (int i = 0; i < n; i++) {
  25.             id[i] = i;
  26.         }
  27.     }
  29.     public int find(int p){
  30.         //返回每个数的连通分量标识
  31.         return id[p];
  32.     }
  34.     public void union(int p,int q){
  35.         //将两个数连接起来，需要将两个连通分量所有的数标识统一
  36.         //需要遍历整个数组
  37.         if (find(p) == find(q)){
  38.             return;
  39.         }
  40.         int pID = find(p);
  41.         int qID = find(q);
  42.         for (int i = 0; i < id.length; i++) {
  43.             if (id[i] == pID){
  44.                 id[i] = qID;
  45.             }
  46.         }
  47.         //每次连接都需要将连通分量数减一
  48.         count--;
  49.     }
  51.     public boolean connected(int p , int q){
  52.         //判断两个数是否连通
  53.         return find(p) == find(q);
  54.     }
  56.     public int count(){
  57.         return count;
  58.     }
  59. }

该算法的主要问题是，每次建立新的连接都需要遍历数组，在极端情况下，当需要建立很多连接时，算法是n的平方级别，这对于大规模问题是不可接受的。

3、quick-union算法

可知，上述算法最主要的问题是每次建立连接时都需要遍历数组，造成了极大地时间开销。因此优化思路是降低建立连接时的开销。
具体思路是采用并查集，让一个连通分量中的所有数都指向一个共同的祖先，那样将建立连接时，只需要一个改动即可。数的组织形式在逻辑上是树形结构。

  1. package union_find;
  3. /**
  4.  * @author zwlstart
  5.  * @create 2020-12-19 20:56
  6.  */
  7. public class QuickUnion {
  8.     //记录每个数的连通分量的标识
  9.     int[] id;
  10.     //记录连通分量的个数
  11.     int count;
  13.     public QuickUnion() {
  15.     }
  17.     public QuickUnion(int n) {
  18.         id = new int[n];
  19.         //连通分量个数初始化为n
  20.         count = n;
  21.         //初始化每个整数的连通分量标识为自己
  22.         for (int i = 0; i < n; i++) {
  23.             id[i] = i;
  24.         }
  25.     }
  27.     public int find(int p){
  28.         //返回每个数的连通分量标识
  29.         //一个连通分量中的所有数都指向共同的祖先，即根节点
  30.         //根节点指向自身
  31.         while (p != id[p]){
  32.             p = id[p];
  33.         }
  34.         return p;
  35.     }
  37.     public void union(int p,int q){
  38.         //将两个数连接起来，需要将两个连通分量所有的数标识统一
  40.         if (find(p) == find(q)){
  41.             return;
  42.         }
  43.         int pID = find(p);
  44.         int qID = find(q);
  46.         //只需要将p的连通分量的根节点指向p的连通分量的根节点即可
  47.         id[pID] = qID;
  49.         //每次连接都需要将连通分量数减一
  50.         count--;
  51.     }
  53.     public boolean connected(int p , int q){
  54.         //判断两个数是否连通
  55.         return find(p) == find(q);
  56.     }
  58.     public int count(){
  59.         return count;
  60.     }
  61. }

该算法与上一个算法相比性能有很大提升，每次插入所需要的时间消耗是类似的树从底部到根节点，即是树的深度。在极端情况下，为一个单项树时，时间复杂度也为n的平方级别。

3、加权quick-union算法

针对上一个问题，主要问题是每次建立连接时树的深度问题，如何降低树的深度是优化算法的关键，即采用加权插入的思想，即每次将小树插入到大树，那么树的深度就会很小，当有n个数时，采用这种插入方式，树的深度最多为log（n）。

  1. package union_find;
  3. /**
  4.  * @author zwlstart
  5.  * @create 2020-12-19 20:56
  6.  */
  7. public class WeightedQuickUnion {
  8.     //记录每个数的连通分量的标识
  9.     int[] id;
  11.     //记录每个连通分量的大小
  12.     int[] num;
  14.     //记录连通分量的个数
  15.     int count;
  17.     public WeightedQuickUnion() {
  19.     }
  21.     public WeightedQuickUnion(int n) {
  22.         id = new int[n];
  23.         //连通分量个数初始化为n
  24.         count = n;
  25.         //初始化每个整数的连通分量标识为自己
  26.         for (int i = 0; i < n; i++) {
  27.             id[i] = i;
  28.         }
  30.         //初始化每个连通分量的大小，初始值均为1
  31.         num = new int[n];
  32.         for (int i = 0; i < n; i++) {
  33.             num[i] = 1;
  34.         }
  35.     }
  37.     public int find(int p){
  38.         //返回每个数的连通分量标识
  39.         //一个连通分量中的所有数都指向共同的祖先，即根节点
  40.         //根节点指向自身
  41.         while (p != id[p]){
  42.             p = id[p];
  43.         }
  44.         return p;
  45.     }
  47.     public void union(int p,int q){
  48.         //将两个数连接起来，需要将两个连通分量所有的数标识统一
  50.         if (find(p) == find(q)){
  51.             return;
  52.         }
  53.         int pID = find(p);
  54.         int qID = find(q);
  56.         //每次将小树插入大树
  57.         if (num[pID] < num[qID]){
  58.             id[pID] = qID;
  59.             num[qID] += num[pID];
  60.         }else{
  61.             id[qID] = pID;
  62.             num[pID] += num[qID];
  63.         }
  65.         //每次连接都需要将连通分量数减一
  66.         count--;
  67.     }
  69.     public boolean connected(int p , int q){
  70.         //判断两个数是否连通
  71.         return find(p) == find(q);
  72.     }
  74.     public int count(){
  75.         return count;
  76.     }
  77. }

加权插入算法已经是非常优秀的算法了，可以保证在任何输入下，每次的建立连接的时间在log(n)级别。

4、最优算法，路径压缩算法

优化的思路是尽量将每次建立连接的时间为常数级别，但这是一件做不到的事情，路径压缩算法的思想是每次遍历的时候，直接将该节点指向根节点。
只需要修改find方法

  1. package union_find;
  3. /**
  4.  * @author zwlstart
  5.  * @create 2020-12-19 20:56
  6.  */
  7. public class CompressionWeightedQuickUnion {
  8.     //记录每个数的连通分量的标识
  9.     int[] id;
  11.     //记录每个连通分量的大小
  12.     int[] num;
  14.     //记录连通分量的个数
  15.     int count;
  17.     public CompressionWeightedQuickUnion() {
  19.     }
  21.     public CompressionWeightedQuickUnion(int n) {
  22.         id = new int[n];
  23.         //连通分量个数初始化为n
  24.         count = n;
  25.         //初始化每个整数的连通分量标识为自己
  26.         for (int i = 0; i < n; i++) {
  27.             id[i] = i;
  28.         }
  30.         //初始化每个连通分量的大小，初始值均为1
  31.         num = new int[n];
  32.         for (int i = 0; i < n; i++) {
  33.             num[i] = 1;
  34.         }
  35.     }
  37.     public int find(int p){
  38.         //返回每个数的连通分量标识
  39.         //一个连通分量中的所有数都指向共同的祖先，即根节点
  40.         //根节点指向自身
  41.         while (p != id[p]){
  42.             //进行路径压缩
  43.             id[p] = id[id[p]];
  44.             p = id[p];
  45.         }
  46.         return p;
  47.     }
  49.     public void union(int p,int q){
  50.         //将两个数连接起来，需要将两个连通分量所有的数标识统一
  52.         if (find(p) == find(q)){
  53.             return;
  54.         }
  55.         int pID = find(p);
  56.         int qID = find(q);
  58.         //每次将小树插入大树
  59.         if (num[pID] < num[qID]){
  60.             id[pID] = qID;
  61.             num[qID] += num[pID];
  62.         }else{
  63.             id[qID] = pID;
  64.             num[pID] += num[qID];
  65.         }
  67.         //每次连接都需要将连通分量数减一
  68.         count--;
  69.     }
  71.     public boolean connected(int p , int q){
  72.         //判断两个数是否连通
  73.         return find(p) == find(q);
  74.     }
  76.     public int count(){
  77.         return count;
  78.     }
  79. }