并查集 (Union-Find)

算法

并查集是一种树形数据结构,用于处理不相交集合的合并及查询问题,支持「查找」和「合并」两种操作,常用于解决连通性问题、最小生成树和动态连通性等问题。

算法讲解

并查集(Union-Find)

介绍

并查集是一种树形的数据结构,用于处理不相交集合(Disjoint Set)的合并及查询问题。它主要支持两种操作:

  1. 查找(Find):确定某个元素属于哪个集合
  2. 合并(Union):将两个集合合并为一个集合

名称"并查集"直接体现了它的核心功能:合并集合与查询元素所属集合。在英文中,它通常被称为"Union-Find"数据结构或"Disjoint-Set"数据结构。

并查集的基本思想是使用树形结构来表示每个集合,树的根节点作为集合的代表元素。

核心特性

  1. 快速查找:能够快速判断两个元素是否属于同一集合
  2. 快速合并:能够快速将两个集合合并为一个
  3. 路径压缩:优化查找操作,使树的高度尽量小
  4. 按秩合并:优化合并操作,减少树的高度增长

基本操作

初始化(MakeSet)

创建n个单元素集合,每个元素初始时都是独立的集合。

查找(Find)

查找元素所属的集合,通常是查找元素所在树的根节点。

合并(Union)

将两个集合合并为一个集合,通常是将一个集合的根节点连接到另一个集合的根节点上。

基础实现

代码实现

Java

▼
Java
复制代码
public class UnionFind { private int[] parent; // 记录每个节点的父节点 private int[] rank; // 记录每个根节点对应树的高度 // 初始化 public UnionFind(int size) { parent = new int[size]; rank = new int[size]; // 初始时,每个元素自成一个集合,父节点指向自己 for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 0; } } // 查找操作(带路径压缩) public int find(int x) { if (parent[x] != x) { // 路径压缩:将x的父节点直接设为根节点 parent[x] = find(parent[x]); } return parent[x]; } // 合并操作(按秩合并) public void union(int x, int y) { int rootX = find(x); int rootY = find(y); // 如果已经在同一集合中,不需要合并 if (rootX == rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 parent[rootY] = rootX; rank[rootX]++; } } // 判断两个元素是否在同一集合 public boolean isConnected(int x, int y) { return find(x) == find(y); } }

Python

▼
Python
复制代码
class UnionFind: def __init__(self, size): # 初始化,每个元素的父节点是自己 self.parent = list(range(size)) # 记录每个根节点对应树的高度 self.rank = [0] * size def find(self, x): # 查找操作(带路径压缩) if self.parent[x] != x: # 路径压缩:将x的父节点直接设为根节点 self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # 合并操作(按秩合并) root_x = self.find(x) root_y = self.find(y) # 如果已经在同一集合中,不需要合并 if root_x == root_y: return # 按秩合并:将秩较小的树连接到秩较大的树下 if self.rank[root_x] < self.rank[root_y]: self.parent[root_x] = root_y elif self.rank[root_x] > self.rank[root_y]: self.parent[root_y] = root_x else: # 秩相同时,随便选一个作为根,并将新根的秩+1 self.parent[root_y] = root_x self.rank[root_x] += 1 def is_connected(self, x, y): # 判断两个元素是否在同一集合 return self.find(x) == self.find(y)

JavaScript

▼
Javascript
复制代码
class UnionFind { constructor(size) { // 初始化,每个元素的父节点是自己 this.parent = Array.from({length: size}, (_, i) => i); // 记录每个根节点对应树的高度 this.rank = Array(size).fill(0); } // 查找操作(带路径压缩) find(x) { if (this.parent[x] !== x) { // 路径压缩:将x的父节点直接设为根节点 this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } // 合并操作(按秩合并) union(x, y) { const rootX = this.find(x); const rootY = this.find(y); // 如果已经在同一集合中,不需要合并 if (rootX === rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 this.parent[rootY] = rootX; this.rank[rootX]++; } } // 判断两个元素是否在同一集合 isConnected(x, y) { return this.find(x) === this.find(y); } }

Go

▼
Go
复制代码
package main type UnionFind struct { parent []int rank []int } // 初始化 func NewUnionFind(size int) *UnionFind { parent := make([]int, size) rank := make([]int, size) // 初始时,每个元素自成一个集合,父节点指向自己 for i := 0; i < size; i++ { parent[i] = i rank[i] = 0 } return &UnionFind{ parent: parent, rank: rank, } } // 查找操作(带路径压缩) func (uf *UnionFind) Find(x int) int { if uf.parent[x] != x { // 路径压缩:将x的父节点直接设为根节点 uf.parent[x] = uf.Find(uf.parent[x]) } return uf.parent[x] } // 合并操作(按秩合并) func (uf *UnionFind) Union(x, y int) { rootX := uf.Find(x) rootY := uf.Find(y) // 如果已经在同一集合中,不需要合并 if rootX == rootY { return } // 按秩合并:将秩较小的树连接到秩较大的树下 if uf.rank[rootX] < uf.rank[rootY] { uf.parent[rootX] = rootY } else if uf.rank[rootX] > uf.rank[rootY] { uf.parent[rootY] = rootX } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 uf.parent[rootY] = rootX uf.rank[rootX]++ } } // 判断两个元素是否在同一集合 func (uf *UnionFind) IsConnected(x, y int) bool { return uf.Find(x) == uf.Find(y) }

C++

▼
C++
复制代码
#include <vector> class UnionFind { private: std::vector<int> parent; // 记录每个节点的父节点 std::vector<int> rank; // 记录每个根节点对应树的高度 public: // 初始化 UnionFind(int size) { parent.resize(size); rank.resize(size, 0); // 初始时,每个元素自成一个集合,父节点指向自己 for (int i = 0; i < size; i++) { parent[i] = i; } } // 查找操作(带路径压缩) int find(int x) { if (parent[x] != x) { // 路径压缩:将x的父节点直接设为根节点 parent[x] = find(parent[x]); } return parent[x]; } // 合并操作(按秩合并) void unite(int x, int y) { int rootX = find(x); int rootY = find(y); // 如果已经在同一集合中,不需要合并 if (rootX == rootY) { return; } // 按秩合并:将秩较小的树连接到秩较大的树下 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { // 秩相同时,随便选一个作为根,并将新根的秩+1 parent[rootY] = rootX; rank[rootX]++; } } // 判断两个元素是否在同一集合 bool isConnected(int x, int y) { return find(x) == find(y); } };

优缺点

优点

  1. 查找和合并操作的平均时间复杂度接近O(1)
  2. 实现简单,易于理解
  3. 空间复杂度低,只需要两个数组
  4. 适用于处理大量动态连通性问题

缺点

  1. 不支持分裂操作(将一个集合分成两个)
  2. 不方便查询集合中的所有元素
  3. 在某些特殊情况下,性能可能退化

应用场景

Kruskal最小生成树算法

在Kruskal算法中,并查集是核心数据结构。该算法按权重从小到大遍历边,使用并查集判断加入某条边是否会形成环,从而高效构建最小生成树。

网络连通性问题

并查集可高效解决动态连通性问题,比如判断网络中两个节点是否连通、社交网络中用户间的关系连接等。当关系变化时,只需执行简单的union操作,判断连通性时使用find操作即可。

等价类划分

在编译器设计、电路分析等领域,并查集可用于等价类识别与合并。当系统发现两个元素等价时执行union操作,需要判断等价关系时使用find操作,这种动态维护等价关系的能力正是并查集的优势所在。

判断无向图中的环

当向无向图中添加边时,如果边的两个端点已在同一个集合中,则添加这条边会形成环。在很多图算法和网络设计问题中都可以使用这一特性。

测验

  1. 并查集主要支持哪两种基本操作?
  2. 路径压缩指的是什么?它有什么好处?
  3. 在一个包含10个元素(1~10)的并查集中,如果我们执行union(1,2), union(3,4), union(1,5), union(6,7), union(8,9), union(7,8),最终会形成多少个不同的集合?
  4. 并查集的合并操作时间复杂度是多少?用了优化后的查询操作时间复杂度是多少?

测验答案

  1. 查找(Find)和合并(Union)操作
  2. 路径压缩是在执行查找操作时,将查找路径上的所有节点都直接连接到根节点的优化技术。这样可以减少树的高度,加速后续的查找操作。
  3. 4个集合。分析:集合1包含元素{1,2,5},集合2包含元素{3,4},集合3包含元素{6,7,8,9},元素10没有参与任何合并操作,单独构成集合4
  4. 同时使用路径压缩和按秩合并时,查找和合并操作的均摊时间复杂度都是O(α(n)),其中α(n)是阿克曼函数的反函数,实际使用中可以近似看作常数。如果只使用路径压缩而不按秩合并,均摊复杂度为O(log n)。

相关的 LeetCode 热门题目

  1. 547. 省份数量 - 使用并查集计算图中的连通分量个数。
  2. 200. 岛屿数量 - 将相邻的陆地合并为一个集合。
  3. 128. 最长连续序列 - 将连续的数字合并到同一集合。
  4. 721. 账户合并 - 根据共同邮箱地址合并账户,并查集的典型应用。

这些题目都是并查集的经典应用场景,可以帮助大家加深对并查集的理解和掌握。