[算法] 并查集

引入

  • 连接问题：一个结点和另一个结点是否相连
    • 网络中节点间的连接状态
    • 微信中任意两个人是否通过好友认识
  • 路径问题：一个结点到另一个结点的路径
  • 集合问题：经常使用并集，需要查询元素是否是一类

     

操作

  • union(p,q)：连接两个元素（放入一个组中）
  • find(p)：p在哪个组中
  • isConnected(p,q)：两个元素是否相连（在一个组中）

实现

  • Quick Find：两个数组，一个存储id号，一个存储组号，
    • find(p)：查询组号，复杂度O(1)
    • union(p,q)：改变元素的组号，复杂度O(n)
    • isConnected(p,q)：两个元素组号是否相同，复杂度O(1)
  • Quick Union：两个数组，一个存储id号，一个存储父节点
    • find(p)：查找根节点编号，复杂度O(h)，h为树的高度
    • union(p,q)：改变父节点值，复杂度O(h)
    • isConnected(p,q)：两个元素是否有相同的根，复杂度O(h)
  • 基于size优化：将元素少的集合并到元素多的集合中，使得层数更少，查询更快
  • 基于rank优化：将层数少的集合合并到层数多的集合中
  • 路径压缩(path compression)：寻找根的时候两步一跳，指向父亲的父亲（时间复杂度近乎O(1)）

示例程序

  • UnionFind1.h：Quick Find
  • UnionFind2.h：Quick Union
  • UnionFind3.h：基于size优化
  • UnionFind4.h：基于rank优化

main.cpp

 1 #include <iostream>
 2 #include "UnionFindTestHelper.h"
 3 
 4 using namespace std;
 5 
 6 int main(){
 7     int n = 10000;
 8     // O(n2)
 9     UnionFindTestHelper::testUF1(n);
10     UnionFindTestHelper::testUF2(n);
11     UnionFindTestHelper::testUF3(n);
12     UnionFindTestHelper::testUF4(n);
13     return 0;
14 }

UnionFindTestHelper.h

 1 #include <iostream>
 2 #include <ctime>
 3 #include "UnionFind1.h"
 4 #include "UnionFind2.h"
 5 #include "UnionFind3.h"
 6 #include "UnionFind4.h"
 7 
 8 using namespace std;
 9 
10 namespace UnionFindTestHelper{
11     void testUF1( int n ){
12         srand( time(NULL) );
13         UF1::UnionFind uf = UF1::UnionFind(n);
14         time_t startTime = clock(); 
15         // 进行n次操作，每次随机选择两个元素进行合并操作 
16         for( int i = 0 ; i < n ; i ++ ){
17             int a = rand()%n;
18             int b = rand()%n;
19             uf.unionElements(a,b);
20         }
21         // 进行n次操作，每次随机选择两个元素查询他们是否属于一个集合
22          for(int i = 0 ; i < n ; i ++ ){
23              int a = rand()%n;
24              int b = rand()%n;
25              uf.isConnected(a,b);
26          }
27          time_t endTime = clock();
28         cout << "UF1, "<<2*n<<" ops, "<<double(endTime - startTime)/
29         CLOCKS_PER_SEC<<" s"<<endl;
30     }
31     void testUF2( int n ){
32         srand( time(NULL) );
33         UF2::UnionFind uf = UF2::UnionFind(n);
34         time_t startTime = clock(); 
35         // 进行n次操作，每次随机选择两个元素进行合并操作 
36         for( int i = 0 ; i < n ; i ++ ){
37             int a = rand()%n;
38             int b = rand()%n;
39             uf.unionElements(a,b);
40         }
41         // 进行n次操作，每次随机选择两个元素查询他们是否属于一个集合
42          for(int i = 0 ; i < n ; i ++ ){
43              int a = rand()%n;
44              int b = rand()%n;
45              uf.isConnected(a,b);
46          }
47          time_t endTime = clock();
48         cout << "UF2, "<<2*n<<" ops, "<<double(endTime - startTime)/
49         CLOCKS_PER_SEC<<" s"<<endl;
50     }
51     void testUF3( int n ){
52         srand( time(NULL) );
53         UF3::UnionFind uf = UF3::UnionFind(n);
54         time_t startTime = clock(); 
55         // 进行n次操作，每次随机选择两个元素进行合并操作 
56         for( int i = 0 ; i < n ; i ++ ){
57             int a = rand()%n;
58             int b = rand()%n;
59             uf.unionElements(a,b);
60         }
61         // 进行n次操作，每次随机选择两个元素查询他们是否属于一个集合
62          for(int i = 0 ; i < n ; i ++ ){
63              int a = rand()%n;
64              int b = rand()%n;
65              uf.isConnected(a,b);
66          }
67          time_t endTime = clock();
68         cout << "UF3, "<<2*n<<" ops, "<<double(endTime - startTime)/
69         CLOCKS_PER_SEC<<" s"<<endl;
70     }
71     void testUF4( int n ){
72         srand( time(NULL) );
73         UF4::UnionFind uf = UF4::UnionFind(n);
74         time_t startTime = clock(); 
75         // 进行n次操作，每次随机选择两个元素进行合并操作 
76         for( int i = 0 ; i < n ; i ++ ){
77             int a = rand()%n;
78             int b = rand()%n;
79             uf.unionElements(a,b);
80         }
81         // 进行n次操作，每次随机选择两个元素查询他们是否属于一个集合
82          for(int i = 0 ; i < n ; i ++ ){
83              int a = rand()%n;
84              int b = rand()%n;
85              uf.isConnected(a,b);
86          }
87          time_t endTime = clock();
88         cout << "UF4, "<<2*n<<" ops, "<<double(endTime - startTime)/
89         CLOCKS_PER_SEC<<" s"<<endl;
90     }
91 }
View Code

UnionFind1.h

 1 #include <iostream>
 2 #include <cassert>
 3 
 4 using namespace std;
 5 
 6 namespace UF1{
 7     
 8 class UnionFind{
 9     private:
10         int* id;
11         int count;
12     public:
13         UnionFind( int n ){
14             count = n;
15             id = new int[n];
16             // 初始化，每个id[d]指向自己 
17             for( int i = 0 ; i < n ; i ++ )
18                 id[i] = i;
19         }
20     ~UnionFind(){
21         delete [] id;
22     }
23     
24     // 查找元素p对应的集合编号 
25     int find( int p ){
26         assert( p >= 0 && p < count );
27         return id[p];
28     }
29     
30     // 查看元素p和q是否属于一个集合
31     // O(1) 
32     bool isConnected( int p , int q ){
33         return find(p) == find(q);
34     }
35     
36     // 合并元素p和q所属的集合
37     // O(n) 
38     void unionElements( int p, int q ){
39         int pID = find(p);
40         int qID = find(q);
41         
42         if( pID == qID )
43             return;
44         for( int i = 0 ;i < count ; i ++){
45             if( id[i] == pID )
46                 id[i] = qID;
47         }
48     }
49 };
50 }
View Code

UnionFind2.h

 1 #include<cassert>
 2 
 3 namespace UF2{
 4     
 5     class UnionFind{
 6         private:
 7             // parent[i]表示第i个元素所指向的父节点 
 8             int* parent;
 9             int count;
10         public:
11             UnionFind(int count){
12                 parent = new int[count];
13                 this->count = count;
14                 for( int i = 0 ; i < count ; i ++)
15                     parent[i] = i;
16             }
17             
18             ~UnionFind(){
19                 delete[] parent;
20             } 
21             
22             // 查找元素p对应的集合编号
23             // O(h)复杂度，h为树的高度
24             int find(int p){
25                 assert( p >= 0 && p < count );
26                 // 不断查询父节点，直到根节点
27                 // 根节点特点：parent[p] = p
28                 while( p != parent[p] )
29                     p = parent[p];
30                 return p; 
31             }
32             // 查看元素p和q是否属于一个集合
33             // O(h)复杂度，h为树的高度
34             int isConnected( int p , int q ){
35                 return find(p) == find(q);
36             }
37             // 合并p和q所属的集合
38             void unionElements(int p, int q){
39                 int pRoot = find(p);
40                 int qRoot = find(q);
41                 if( pRoot == qRoot )
42                     return;
43                 parent[pRoot] = qRoot;
44             } 
45     };
46     
47 }
View Code

UnionFind3.h

 1 #include<cassert>
 2 
 3 namespace UF3{
 4     
 5     class UnionFind{
 6         private:
 7             int* parent; // parent[i]表示第i个元素所指向的父节点
 8             int* sz; // sz[i]表示以i为根的集合中的元素个数 
 9             int count;  // 数据个数 
10             
11         public:
12             UnionFind(int count){
13                 parent = new int[count];
14                 sz = new int[count]; 
15                 this->count = count;
16                 for( int i = 0 ; i < count ; i ++){ 
17                     parent[i] = i;
18                     sz[i] = 1;
19                 } 
20             }
21             
22             ~UnionFind(){
23                 delete[] parent;
24                 delete[] sz;
25             } 
26             
27             // 查找元素p对应的集合编号
28             // O(h)复杂度，h为树的高度
29             int find(int p){
30                 assert( p >= 0 && p < count );
31                 // 不断查询父节点，直到根节点
32                 // 根节点特点：parent[p] = p
33                 while( p != parent[p] )
34                     p = parent[p];
35                 return p; 
36             }
37             // 查看元素p和q是否属于一个集合
38             // O(h)复杂度，h为树的高度
39             int isConnected( int p , int q ){
40                 return find(p) == find(q);
41             }
42             // 合并p和q所属的集合
43             void unionElements(int p, int q){
44                 int pRoot = find(p);
45                 int qRoot = find(q);
46                 if( pRoot == qRoot )
47                     return;
48                 if( sz[pRoot] < sz[qRoot] ){
49                 parent[pRoot] = qRoot;
50                 sz[qRoot] += sz[pRoot];
51             }else{
52                 parent[qRoot] = pRoot;
53                 sz[pRoot] += sz[qRoot];
54             }
55         } 
56     };
57 }
View Code

UnionFind4.h

 1 #include<cassert>
 2 
 3 namespace UF4{
 4     
 5     class UnionFind{
 6         private:
 7             int* parent;  // parent[i]表示第i个元素所指向的父节点
 8             int* rank;  // rank[i]表示以i为根的集合中所表示树的层数(路径压缩中不维护其含义) 
 9             int count;  // 数据个数 
10             
11         public:
12             UnionFind(int count){
13                 parent = new int[count];
14                 rank = new int[count]; 
15                 this->count = count;
16                 for( int i = 0 ; i < count ; i ++){ 
17                     parent[i] = i;
18                     rank[i] = 1;
19                 } 
20             }
21             
22             ~UnionFind(){
23                 delete[] parent;
24                 delete[] rank;
25             } 
26             
27             // 查找元素p对应的集合编号
28             // O(h)复杂度，h为树的高度
29             int find(int p){
30                 assert( p >= 0 && p < count );
31                 // 不断查询父节点，直到根节点
32                 // 根节点特点：parent[p] = p
33                 while( p != parent[p] ){
34                     // 路径压缩 
35                     parent[p] = parent[parent[p]];
36                     p = parent[p];
37                 }
38                 return p; 
39 //                递归实现的路径压缩 
40 //                if( p != parent[p] )
41 //                    parent[p] = find(parent[p]);
42 //                return parent[p];
43             }
44             // 查看元素p和q是否属于一个集合
45             // O(h)复杂度，h为树的高度
46             int isConnected( int p , int q ){
47                 return find(p) == find(q);
48             }
49             // 合并p和q所属的集合
50             void unionElements(int p, int q){
51                 int pRoot = find(p);
52                 int qRoot = find(q);
53                 if( pRoot == qRoot )
54                     return;
55                 if( rank[pRoot] < rank[qRoot] ){
56                     parent[pRoot] = qRoot;
57                 }
58                 else if( rank[qRoot] < rank[pRoot] )
59                     parent[qRoot] = pRoot;
60                 else{ // rank[qRoot] == rank[pRoot]
61                     parent[pRoot] = qRoot;
62                     rank[qRoot] += 1;
63                 }
64             }
65     };
66 }
View Code

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cxc1357/p/12244377.html