Linux 中的并查集¶
- 日期:
2024 年 6 月 21 日
- 作者:
Xavier <xavier_qy@163.com>
什么是并查集，它有什么用？¶
并查集是一种用于处理不相交集合的合并和查询的数据结构。并查集支持的主要操作有：
- 初始化：将每个元素重置为一个独立的集合，其中
每个集合的初始父节点指向自身。
- 查找：确定特定元素属于哪个集合，通常通过
返回该集合的“代表元素”来完成。此操作用于检查两个元素是否在同一集合中。
合并：将两个集合合并为一个。
作为一种用于维护集合（组）的数据结构，并查集常用于解决离线查询、动态连通性和图论相关的问题。它也是 Kruskal 算法计算最小生成树的关键组成部分，这在网络路由等场景中至关重要。因此，并查集被广泛引用。此外，并查集还在符号计算、寄存器分配等方面有应用。
空间复杂度：O(n)，其中 n 是节点数量。
时间复杂度：使用路径压缩可以降低查找操作的时间复杂度，而使用按秩合并可以降低合并操作的时间复杂度。这些优化将每次查找和合并操作的平均时间复杂度降低到 O(α(n))，其中 α(n) 是反阿克曼函数。在实际应用中，这大致可以被视为常数时间复杂度。
本文档介绍 Linux 并查集实现的使用。有关并查集性质和实现的更多信息，请参阅：
Linux 并查集实现¶
Linux 的并查集实现位于文件“lib/union_find.c”中。要使用它，请“#include <linux/union_find.h>”。
并查集数据结构定义如下：
struct uf_node {
struct uf_node *parent;
unsigned int rank;
};
在此结构中，`parent` 指向当前节点的父节点。`rank` 字段表示当前树的高度。在合并操作期间，秩较小的树会连接到秩较大的树下面，以保持平衡。
初始化并查集¶
您可以使用静态或初始化接口完成初始化。将父指针初始化为指向自身，并设置秩为 0。示例：
struct uf_node my_node = UF_INIT_NODE(my_node);
或
uf_node_init(&my_node);
查找并查集的根节点¶
此操作主要用于判断并查集中两个节点是否属于同一集合。如果它们具有相同的根，则它们在同一集合中。在查找操作期间，会执行路径压缩以提高后续查找操作的效率。示例：
int connected;
struct uf_node *root1 = uf_find(&node_1);
struct uf_node *root2 = uf_find(&node_2);
if (root1 == root2)
connected = 1;
else
connected = 0;
合并并查集中的两个集合¶
要在并查集中合并两个集合，首先找到它们各自的根节点，然后根据根节点的秩将较小的节点连接到较大的节点。示例：
uf_union(&node_1, &node_2);