深入理解并查集：原理、实现与应用

深入理解并查集：原理、实现与应用

引用

CSDN

1.

https://blog.csdn.net/2302_77582029/article/details/146291059

并查集：原理、实现与应用

引言

并查集（Disjoint Set Union, DSU）是一种用于处理不相交集合合并与查询操作的数据结构。它广泛应用于图论、网络连接问题以及动态连通性问题。本文将详细介绍并查集的原理、实现方法、优化技巧以及典型应用场景，帮助读者全面掌握这一重要数据结构。

1. 并查集的定义与原理

1.1 定义

并查集是一种树形数据结构，用于维护一组不相交的集合，支持以下两种操作：

• 查找（Find）：确定某个元素所属的集合。
• 合并（Union）：将两个集合合并为一个集合。

1.2 核心思想

• 每个集合用一棵树表示，树的根节点作为集合的代表。
• 通过路径压缩和按秩合并优化操作效率。

1.3 示例

假设有5个元素：{0, 1, 2, 3, 4}，初始时每个元素都是一个独立的集合：

0   1   2   3   4

执行以下操作：

1. Union(0, 1)：将0和1合并。

0
|
1

2. Union(2, 3)：将2和3合并。

2
|
3

3. Union(1, 3)：将1和3合并。

  0
 / \
1   2
    |
    3

4. Find(3)：查找3的根节点，结果为0。

2. 并查集的实现

以下是并查集的C++实现代码，包括路径压缩和按秩合并优化。

2.1 代码实现

#include <iostream>
#include <vector>

class DSU {
private:
    std::vector<int> parent; // 父节点数组
    std::vector<int> rank;   // 秩数组（树的高度）

public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 1); // 初始时每个集合的秩为1
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始时每个节点的父节点是自己
        }
    }

    // 查找操作（带路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并操作（带按秩合并）
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return; // 已经在同一集合中

        // 按秩合并
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // 判断两个元素是否在同一集合中
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    DSU dsu(10);
    dsu.unionSets(1, 2);
    dsu.unionSets(2, 3);
    dsu.unionSets(4, 5);
    std::cout << "1 和 3 是否连通: " << (dsu.isConnected(1, 3) ? "是" : "否") << std::endl;
    std::cout << "1 和 4 是否连通: " << (dsu.isConnected(1, 4) ? "是" : "否") << std::endl;
    return 0;
}

2.2 代码解析

• 初始化：每个元素的父节点是自己，秩为1。
• 查找操作：通过递归找到根节点，并进行路径压缩。
• 合并操作：将两个集合的根节点合并，按秩合并避免树过高。
• 连通性判断：通过查找操作判断两个元素是否在同一集合中。

3. 并查集的应用场景

3.1 图的连通性问题

• Kruskal算法：用于最小生成树中判断边是否会形成环。
• 连通分量：用于统计图中的连通分量数量。

3.2 动态连通性问题

• 网络连接：实时判断两个设备是否连通。
• 社交网络：判断两个人是否属于同一个社交圈子。

3.3 图像处理

• 像素连通性：用于图像分割中判断像素是否属于同一区域。

4. 并查集的优化

4.1 路径压缩

• 在查找操作中，将节点的父节点直接指向根节点，减少后续查找的时间。

• 示例：

查找前：
  0
 / \
1   2
   / \
  3   4

查找3后：
    0
  / | \
 1  2 3
      \
       4

4.2 按秩合并

• 在合并操作中，将较小的树合并到较大的树中，避免树的高度过高。

• 示例：

合并前：
  0        2
 /        / \
1        3   4

合并后：
    0
  / | \
 1  2 3
      \
       4

5. 并查集的时间复杂度

• 查找操作：接近O(1)。
• 合并操作：接近O(1)。
• 总体时间复杂度：O(α(n))，其中α(n)是反阿克曼函数，增长非常缓慢。

6. 总结

并查集是一种高效的数据结构，适用于处理不相交集合的合并与查询问题。通过路径压缩和按秩合并优化，其操作的时间复杂度接近常数级别。掌握并查集的原理和实现方法，可以帮助我们更好地解决实际问题。