前言

C++ 代码实例：并查集简单创建工具。

代码仓库

代码

说明

  • 简单地创建并查集
  • 注释有详细的步骤解析
  • 还可优化的点：使用cmake；使用右值传递复杂容器减小开销

注：半个晚上完成，大概测试了下

main.cpp

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using std::cout;
using std::endl;
using std::pair;
using std::sort;
using std::unordered_map;
using std::vector;

// 并查集类
class DisjointSet
{
public:
    // 构造并查集
    // 参数：等价关系元素值的大小/范围，等价关系集合向量
    DisjointSet(const int &e_q_s, const vector<pair<int, int>> &e_r_v) : eq_rel_size(e_q_s), eq_rel_vec(e_r_v)
    {
        // 1. 初始化元素父节点向量，大小是等价关系元素值的大小/范围，每个元素的父节点约定为自身
        this->parent_vec.resize(this->eq_rel_size); // 元素父节点的向量的大小是等价关系元素值的大小/范围
        for (int i = 0; i < this->eq_rel_size; ++i)
        {
            parent_vec[i] = i;
        }

        // 2. 初始化元素深度向量，大小是等价关系元素值的大小/范围，每个元素作为根节点约定为0即第0层
        // 合并操作依据树的深度优化，即优先将深度大的树的根挂接到深度小的树的根
        this->depth_vec.resize(this->eq_rel_size, 0);

        // 3. 按照字典序排序等价关系集合向量
        sort(this->eq_rel_vec.begin(), this->eq_rel_vec.end());

        // 4. 合并集合
        for (const auto &eq_rel_pair : eq_rel_vec) // 对每一个等价关系集合，如：{1, 2}
        {
            // 4.1 分别查找两关系元素的根节点
            int first_root = this->find_parent(eq_rel_pair.first);
            int second_root = this->find_parent(eq_rel_pair.second);

            // 4.2 依据根节点情况合并挂接
            if (first_root == second_root) // 相等不操作
            {
                continue;
            }
            else // first_root != second_root
            {
                if (this->depth_vec[first_root] < this->depth_vec[second_root]) // 优先将深度大的树的根挂接到深度小的树的根
                {
                    this->parent_vec[first_root] = second_root;
                }
                else if (this->depth_vec[first_root] > this->depth_vec[second_root])
                {
                    this->parent_vec[second_root] = first_root;
                }
                else // == 树的深度相等，约定将第二个根挂接到第一个根，第一个根的深度加深一层
                {
                    this->parent_vec[second_root] = first_root;
                    ++this->depth_vec[first_root];
                }
            }
        }

        // 5. 构建结果
        unordered_map<int, vector<int>> root_vec{}; // 哈希表，记录 根节点值-该根节点下的元素向量，一个向量是一棵新树
        for (int i = 0; i < this->eq_rel_size; ++i) // 遍历元素值
        {
            int root = this->find_parent(i); // 取根节点
            root_vec[root].push_back(i);
        }

        for (const pair<int, vector<int>> &pair_tree : root_vec) // 遍历每棵树，加入到结果集
        {
            this->disjoint_set.insert(this->disjoint_set.begin(), pair_tree.second);
        }
    }

    // 获取并查集
    inline vector<vector<int>> get_disjoint_set() const
    {
        return this->disjoint_set;
    }

    // 打印并查集
    inline void print_disjoint_set() const
    {
        cout << "并查集: " << endl;
        for (const vector<int> set : this->disjoint_set)
        {
            for (const int num : set)
            {
                cout << num << " ";
            }
            cout << endl;
        }

        return;
    }

private:
    const int eq_rel_size;             // 等价关系元素值的大小/范围
    vector<pair<int, int>> eq_rel_vec; // 等价关系集合向量

    vector<int> parent_vec; // 记录元素父节点的向量
    vector<int> depth_vec;  // 记录元素深度的向量，约定元素值/树的根是索引，根的深度从0、1往上加

    vector<vector<int>> disjoint_set; // 并查集，并查集类固有的本质内容

    // 递归查找当前元素值的根节点
    int find_parent(int x)
    {
        // 1. 递归逻辑
        // 如果不是，parent[x] != x，则使用当前节点的父节点作为参数，调用当前函数，递归继续找爷节点：find_parent(parent[x])
        // 把找到的根节点记录在查找路径中每个节点的 元素父节点的向量 中：parent_vec[x] =
        // 相当于把该些节点，都挂接到根节点上，树变得扁平

        // 即路径压缩优化：在并查集中，每个元素都有一个父节点，通常在查找操作中，我们会沿着父节点链一直向上找到根节点
        // 这个过程就是在寻找元素所在集合的过程。但是，在普通的查找操作中，路径的长度可能会很长，导致后续的查找操作效率较低。
        // 路径压缩是一种优化技术，它的思想是：当我们在进行查找操作时，不仅找到元素所在集合的根节点，
        // 还顺便将经过的所有节点的父节点都设置为根节点。这样，当下次再次查找这些节点时，路径就会更短，查找效率就会更高。

        // 如：1为根节点，23为子节点，有1 - 2 - 3的三层树，从叶节点3开始找，找到1根节点，然后依次递归返回把2、3的根节点设置为1
        // 成为1 - 2，1 - 3的两层树
        if (parent_vec[x] != x)
        {
            parent_vec[x] = find_parent(parent_vec[x]);
        }

        // 1. 递归出口
        // 如果x的父节点是自己，说明它是根节点，返回
        // parent_vec[x] == x
        // 把return放在if会有到不了该条件if的警告：control reaches end of non-void function [-Wreturn-type]
        return parent_vec[x];
    }
};

int main()
{
    const int eq_rel_size = 9;                                                                          // 等价关系元素值的大小/范围
    const vector<pair<int, int>> eq_rel_vec = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {0, 2}, {4, 6}, {0, 8}}; // 等价关系集合向量，内容必须是0~ eq_rel_size - 1（并查集类的逻辑定义了）

    DisjointSet ds(eq_rel_size, eq_rel_vec); // 并查集对象
    ds.print_disjoint_set();                 // 打印并查集

    return 0;
}

Makefile

1
2
3
4
5
6
7
8
9
.PHONY : all
all : main.exe

main.exe : main.cpp
	g++ -o $@ $^

.PHONY : clean
clean :
	del *.exe

结果

在这里插入图片描述

总结

C++ 代码实例：并查集简单创建工具。

参考资料

  • 学校《高级算法设计与分析》课程课件的算法思路

作者的话

  • 感谢参考资料的作者/博主
  • 作者：夜悊
  • 版权所有，转载请注明出处，谢谢~
  • 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
  • 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
  • 文章在认识上有错误的地方, 敬请批评指正
  • 望读者们都能有所收获