（详细版）并查集---图论

• 并查集的概念：
  并查集(Union-Find)是一种可以用来判断同属一个集合中相互关联的元素属于几个集合，也可以用来判断图结构中的两点是否是连通, 它也是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

• 并查集的算法介绍
  联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：

  • Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

• 并查集的应用
  1，一般来说，可以用来合并集合元素，确定结合数量，查找元素处于哪个集合的位置。
  2. 在图结构里，确定两个结点是否处于连通状态(解决动态连通性)，尤其在图的应用中广泛涉及。

  在解决动态连通性的场景里，我们需要思考两个问题，第一，给出的结点是否连通，第二，如果连通，则路径不需要记录，若不连通，则路径需要记录。

• 并查集的常见结构

  • 基本函数(API):
    • 用于初始化-----Init(n) ;
    • 用于查找结点祖先-----Find(i) ;
    • 用于合并两结点并建立联系-----Union( i, j) ;
  • 存储结构:
    • 用于存储每一个结点元素的祖先结点-----fa[MAXSIZE] ;

• 分析并查集，建立模型

假设存在四个互不相通的结点，并将相通的那部分结点称为族

1）首先实现初始化,使对应的结点指向自己，形成独立的元素

void Init(int n) //初始化
    {        
       int i;
	     fa[0] = MAXSIZE;//设置哨兵 
	     for(i=1; i<=n; i++){
		     fa[i] = i;//让所有结点指向自己 
		 }
    }
1
2
3
4
5
6
7
8

2）然后实现查找操作（未进行路径压缩），查找祖先结点
例如：如果插入结点5必须查找到结点4，而根据以下代码需要从结点1开始，逐渐向右查找，直到找到4结点(祖先结点)，返回结点4

int Find(int i)//查找 //未进行路径压缩
     {
        if(i==fa[i])//递归出口，当达到了祖先位置，就返回祖先 
   	      return i;
        else
     	  return Find(fa[i]);//不段向前查找祖先 
     }
1
2
3
4
5
6
7

但这样的算法在结点数量较大的时候，过于复杂，需要一个一个查找才能够找到祖先结点，为何不直接在每次查找的同时改变祖先结点，直接找到它呢？诶，这里就需要通过路径压缩的方式构造一种新的结构了。

但是哪种结构对于查找和修改的效率最高？毫无疑问是树，因此考虑如何将结点和族的关系以树的形式表现出来。

如图所示：

改进后的代码部分：

//进行路径压缩 
    int Find(int i)//查找 
    {
       if(i==fa[i])//递归出口，当达到了祖先位置，就返回祖先
   	      return i;
       else{
     	  fa[i] = Find(fa[i]);//不段向前查找祖先,并保存祖先 
           return fa[i];
       }
    }
1
2
3
4
5
6
7
8
9
10

当然，也可不用递归的方法，改用迭代也行

int Find(int i)//查找
    {
       while(fa[i] != i){//直到找到祖先结点
           fa[i] = fa[fa[i]];
           i = fa[i];     
       }
       return i;
    }
1
2
3
4
5
6
7
8

3）合并两结点，建立两个结点的父子关系

注：当 find_i==find_j 时，可以说明形成了连通路，不进行合并操作

  void Union(int i, int j)//合并i, j 
    {
	   int find_i = Find(i);//找到i的祖先 
	   int find_j = Find(j);//找到j的祖先 
	
	   if(find_i==find_j)//导致形成连通路
	      return;
	
	   fa[find_i] = find_j; //i的祖先指向j的祖先 
    } 

1
2
3
4
5
6
7
8
9
10
11

以下是完整代码：

#include<stdio.h>
#define MAXSIZE 30000

int fa[MAXSIZE];//存储每一个元素的父结点 

void Init(int n)//初始化 
{
	int i;
	fa[0] = MAXSIZE;//设置哨兵 
	for(i=1; i<=n; i++){
		fa[i] = i;//让所有结点指向自己 
	}
	
}
//未进行路径压缩 
int Find(int i)//查找 
{
     if(i==fa[i])//递归出口，当达到了祖先位置，就返回祖先 
   	    return i;
     else
     	return Find(fa[i]);//不段向前查找祖先 
}

//进行路径压缩 
int Find(int i)//查找 
{
     if(i==fa[i])//递归出口，当达到了祖先位置，就返回祖先
   	    return i;
     else{
     	fa[i] = Find(fa[i]);//不段向前查找祖先,并保存祖先 
     	
     	return fa[i];
     }
}
//非递归方法
int Find(int i)//查找
{
     while(fa[i] != i){//直到找到祖先结点
           fa[i] = fa[fa[i]];
           i = fa[i];     
     }
     return i;
}

void Union(int i, int j)//合并i, j 
{
	int find_i = Find(i);//找到i的祖先 
	int find_j = Find(j);//找到j的祖先 
	
	if(find_i==find_j)//导致形成连通路
	     return;
	
	fa[find_i] = find_j; //i的祖先指向j的祖先 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

• 并查集的现实应用

  • 当然现实生活中的情况比上述情况复杂多了，比如出现以下情况
    
    还有这种情况
    
    等等。
    注意：这里的结构顺序是自下而上的，因为在并查集算法里，多个子结点可以指向一个祖先结点，但不可能一个子结点指向多个指向结点

  • 所以，我们仍需要对算法进行更多的修改和精进，对于大数据类型，找到合适的数据结构，然后有针对性的进行改进，得到更高效的算法，例如Quick-Union算法及其多种改进算法，最终使得算法的复杂度降低到了近乎线性复杂度。

• 并查集的相关例题（leetcode）

  • 有 n 个结点，其中一些彼此相连，另一些没有相连。种族 是一组直接或间接相连的结点，组内不含其他没有相连的结点。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个结点和第 j 个结点直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 种族 的数量。
    注：该题有其他方法，在这里我们用并查集去解决问题

int count;
int *fa;
void Init(int n)
{
    count = n;
    fa = (int* )calloc(n, sizeof(int));//申请空间
    for(int i=0; i<n; i++)
      fa[i] = i;  
}

int Find(int i)
{
    while(i != fa[i]){
        fa[i] = fa[fa[i]];
        i = fa[i];
    }
    return i;
}

void Union(int i, int j)//合并i, j 
{
	int find_i = Find(i);//找到i的祖先 
	int find_j = Find(j);//找到j的祖先 
	
	if(find_i==find_j)//导致形成连通路
	     return;
	
	fa[find_i] = find_j; //i的祖先指向j的祖先 
	count--;
} 


int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
   Init(isConnectedSize);//初始化
   for(int i=0; i<isConnectedSize; i++){//遍历全部结点
       for(int j=i+1; j<isConnectedSize; j++){
             if(isConnected[i][j] == 1){
                 Union(i, j);
             }
       }
   } 
   return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 并查集的现实问题情况
  • 这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果，只能用并查集来描述，因此并查集结构具备节省空间，快速计算的优点。