[数据结构与算法]一篇文章彻底搞懂并查集！

一篇文章彻底搞懂并查集！

最近在复习数据结构，又复习到了并查集 - - ，复习完之后发现之前写的那个笔记写的什么鬼，然后我就把知识点重新整理一下，顺便水一篇博客（bushi）。本文章是结合个人见解整理的并查集知识，如果有不当的地方欢迎交流指出。

前置基础知识

1. 树的概念：（这里以二叉树为例）

   • 树(tree)是n**(n>0)**个结点的有限集。
   • 树中每个结点对应两个指针，其中一个指针指向左子树，另一个指针指向右子树。

2. 森林的概念：

   • 森林(forest)是m (m≥0) 棵互不相交的树的 集合。（区别于现实的独木不成林）

3. 树的储存结构：（这里只介绍目前笔者常见两种）

   1. 孩子兄弟表示法：

• 这个结构我在刷题用的很多，放在二叉树里就是定义一个结点，其中开辟一个储存数据的空间，接着开辟储存左右孩子的指针的空间，结点定义如下：

  typedef struct TreeNode {
  	elemtype data;
      struct TreeNode *left;
      struct TreeNode *right;
  } NodeType, *CSTree;

2. 双亲表示法：

• 每个结点都有独一无二的下标，通过该下标可以直接找到该结点以及对应的双亲结点。简单来讲就是开辟了一个数组，下标唯一标识一个结点，内容指向其双亲结点。

• 这个结构在遇到并查集题目前见过的不多，时间久了就忘记了，但是这个结构在并查集中很重要！

3. 并查集使用双亲表示法的原因是：

   1. 每个结点都有独一无二的下标，通过该下标可以直接找到该结点以及对应的双亲结点，而孩子兄弟表示法（上一种方法）则不能做到。

   2. 双亲表示法可以更好的表示森林，而孩子兄弟法需要开辟额外空间记录根结点来记录森林。

并查集要解决的问题是

?

? 连通性问题。 举个栗子，假如我们现在在A点，现在A可以走到B，B又可以走到C，问我们是否可以走到C点，这个问题就可以用并查集来解决。

? 当然会遇到一些具体问题，比如判断成环问题，与图结合有关问题等，我们遇到具体问题需要具体分析。

几种并查集版本

quick_find：

• 思路：如果两个结点连通，那么所有连通的结点就统一都用一个结点的编号标记。类似于染色分队，只要连通的都用同一个颜色标记，我就能判断两个结点是否连通了。如下图所示，我们可以根据颜色区分任意两个人是否连通（属于同一个队伍）了。

• 举个栗子，现在我们定义了（0 - 9）十个结点，每个结点的双亲如下图所示。现在我们要将下标5和下标9连通，可以看到下标5的双亲为1，下标9的双亲为8。那么此时我们要做的就是把双亲为1的结点更新其双亲为8。如下图所示：

• 代码：

int quick_find(int* parents,int node)
{
    return parents[node];
}

void merge(int* parents, int size, int a, int b)
{
    if(parents[a] == parents[b]) return;
    int target = parents[b];
    for(int i = 0; i <= size; i++)
        if(parents[i] == target) parents[i] = parents[a];
}

• 时间复杂度：

  • 查找：O（1），下标对应双亲就是根结点，无需往上遍历。
  • 合并：O（n），每次合并都要遍历数组，将符合条件的结点的双亲更新。

quick_union：

• 思路：如果两个结点连通，我们将其中一个结点的根结点设置为其连通结点的根结点的双亲即可。

• 举个栗子，现在有两棵树（如下图所示），我们这次还是要将下标为5的结点与下标为9的结点连通。根据quick_union算法，我们找到下标5的根结点为1，下标9的根结点为8，此时我们只要把下标为1的双亲更新为8即可。

• 代码：

  int find_root(int* parents, int node)
  {
      while(parents[node] != node) node = parents[node];
      return node;
  }
  
  void quick_union(int* parents, int a, int b)
  {
      parents[find_root(parents, b)] = find_root(parents, a);
  }
  

• 时间复杂度：

  • 查找：O（k），需要一直寻找双亲直至找到根结点，k为树的高度。

  • 合并：O（k），无需遍历数组，只需寻找树的根结点，然后更新其中一个结点双亲的值即可。

weighted_quick_union：

• 功能：quick_union 的改良版，解决树退化成链表，降低查找效率的问题。

• quick_union 弊端分析以及解决方法：

  • 假设有如下场景：

    ? 有n（n > 0）个结点，我们现在要把0和1连通，1和2连通，2和3连通，3和4连通…（如下图所示）。此时我们可以看到，4结点所在树已经退化成了链表结构，这时我们进行查找，时间复杂度为O（n），效率极低。

• 回到刚刚的情况（上图所示），第二步合并0和2中，假如我们在合并操作的时候选择1为2的根结点的话，这样树就不会退化成链表了，因此我们需要将合并操作进行改进。
  
  

• 改进思路：

  ? 增加一个数组，用来记录结点的权重（权重可以为该结点所在子树所有结点的数量，也可以为该结点的高度。本文采用结点数量作为权重）。在合并操作中，我们需要把权重小的根结点的双亲设置成权重大的根结点的双亲，这样就可以避免树退化成链表的情况了。

• quick_union 和 weighted_quick_union 的比较：

• 代码：

  typedef struct Set
  {
      int* data; // 储存结点的双亲
      int* weight; // 储存结点的权重
      int size; // 储存结点的数量
  }Set;
  
  // 初始化结构体
  Set *init_set(int n)
  {
      Set *set = (Set *)malloc(sizeof(Set));
      set -> data = (int *)malloc(sizeof(int) * (n + 5));
      set -> weight = (int *)malloc(sizeof(int) * (n + 5));
      set -> size = n;
      for(int i = 0; i < (n + 5); i++)
          set -> data[i] = i, set -> weight[i] = 1;
      return set;
  }
  
  // 释放结构体
  void free_set(Set* set)
  {
      free(set -> data);
      free(set -> weight);
      free(set);
  }
  
  int find_root(Set* set, int node)
  {
      if(node == set -> data[node]) return node;
      return find_root(set, set -> data[node]);
  }
  
  void quick_union_weighted(Set* set, int a, int b)
  {
      int roota = find_root(set, a);
      int rootb = find_root(set, b);
      if(roota == rootb) return; //如果根结点相同，则返回。
      
      //根据权重进行对应操作
      //这里权重采用结点子树的结点数作为权重
      if(set -> weight[roota] < set -> weight[rootb])
      {
          /*将父结点的权重加上其子结点的权重*/
          set -> weight[rootb] += set -> weight[roota];
          /*更新父结点*/
          set -> data[roota] = rootb;
      }
      else
      {
          /*将父结点的权重加上其子结点的权重*/
          set -> weight[roota] += set -> weight[rootb];
          /*更新父结点*/
          set -> data[rootb] = roota;
      }
  }
  

• 时间复杂度：

  • 查找：O（k），需要一直寻找双亲直至找到根结点，k为树的高度，经过权重优化后，基本不会出现O（n）（n为结点数量）的极端情况。

  • 合并：O（k），无需遍历数组，只用更新其中一个结点双亲的值即可。

路径压缩优化：

• 思路：

  回到 quick_union 弊端分析以及解决方法（如下图所示）：

? quick_union的弊端所构建的树在于极端情况下会退化成链表，我们可以看到，经过weighted_quick_union改良后，树的高度明显减小。

? 我们知道，树的高度减小，意味着我们查找的时间效率提升。那么有没有一种方法，使得我们树的高度尽可能小呢？（非常理想的情况：连通的所有结点的双亲都指向同一个根结点），如下图所示：

? 那如果我们在查找双亲的时候，顺便把图中查找过的结点的双亲结点全部指向根结点，那这颗树不就变得很扁平了？

? 这就是路径压缩算法的原理。

• 代码：

  其实也非常简单，我们只用在查找过程中递归返回更新每一个结点的双亲结点为根结点就可以了。

  int find_root2(Set* set, int node)
  {
      if(node == set -> data[node]) return node;
      /*递归返回，将双亲结点的双亲更新为根结点即可*/
      return set -> data[node] = find_root2(set, set -> data[node]);
  }
  

• 时间复杂度：

  • 查找：O（1），需要一直寻找双亲直至找到根结点，k为树的高度。经过路径压缩优化后，最优为O（1）。

  • 合并：O（1），只用更新其中一个结点双亲的值即可。经过路径压缩优化后，最优为O（1）。

相关题目：

1. 冗余连接
2. 冗余连接2
3. 岛屿数量
4. 被围绕的区域
5. 最长连续序列

参考资料

1. 数据结构——树和森林
2. 并查集(Union-Find)算法介绍
3. 学习笔记：图解，以小白的思维角度详细理解并查集（c++代码示例）