并查集是什么？并查集的路径压缩-js教程-PHP中文网

并查集是什么？并查集的路径压缩

幻夢星雲

发布： 2025-08-22 11:25:01

原创

219人浏览过

并查集是一种用于管理元素分组的树形数据结构，支持高效的合并（union）和查找（find）操作，判断两元素是否同属一个集合；初始化时每个元素自成集合，通过parent数组记录父节点，初始时parent[i]=i；查找操作通过递归找到根节点，路径压缩在查找过程中将沿途节点直接连接到根节点，显著降低后续查找的时间复杂度；合并操作通过将一棵树的根连接到另一棵树的根实现集合合并，结合按秩合并（利用rank数组记录树高上界，优先将较矮树挂到较高树下）可有效维持树的平衡，防止退化为链表；路径压缩虽改变实际树高并使rank不再精确反映真实高度，但其仍可作为上界指导合并，确保性能稳定；两者结合后，查找与合并的均摊时间复杂度接近o(1)；并查集常用于判断图的连通性、计算连通分量、朋友圈问题及kruskal最小生成树算法；其空间复杂度为o(n)，主要消耗于parent和rank两个数组，其中n为元素数量。

并查集是什么？并查集的路径压缩

并查集，简单来说，就是用来管理元素分组情况的数据结构。它能高效地进行合并（union）和查询（find）操作，判断两个元素是否属于同一组。路径压缩是优化并查集性能的关键技巧，能显著降低后续操作的时间复杂度。

并查集的实现与路径压缩

并查集的核心思想是使用树形结构来表示集合。每个集合对应一棵树，树的根节点代表这个集合。

初始化： 初始时，每个元素都是一个独立的集合，即每个元素都是一棵只包含自己的树。我们可以用一个数组
```
parent
```
登录后复制
来记录每个元素的父节点，初始时
```
parent[i] = i
```
登录后复制
。
```
def make_set(n):
    parent = list(range(n))
    return parent
```
登录后复制

查找（Find）： 查找操作用于找到元素所属集合的根节点。

def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

登录后复制

合并（Union）： 合并操作用于将两个集合合并成一个集合。通常，我们将一棵树的根节点指向另一棵树的根节点。
```
def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
```
登录后复制
在上面的
```
union
```
登录后复制
函数中，
```
rank
```
登录后复制
数组用于优化合并操作，它记录了树的高度（或者说是树的深度的一个上界）。通过将高度较低的树连接到高度较高的树上，可以尽量保持树的平衡，避免出现极端情况下树退化成链表的情况。这部分叫做“按秩合并”。
路径压缩： 路径压缩是一种优化查找操作的技巧。在查找过程中，我们将访问过的每个节点直接指向根节点。这样，下次查找这些节点时，就可以直接找到根节点，而不需要沿着路径向上查找。

LobeHub
LobeChat brings you the best user experience of ChatGPT, OLLaMA, Gemini, Claude

201

查看详情
```
def find(parent, i):
    if parent[i] == i:
        return i
    parent[i] = find(parent, parent[i]) # 路径压缩
    return parent[i]
```
登录后复制
路径压缩的实现非常简单，只需要在
```
find
```
登录后复制
函数中，在递归返回之前，将当前节点的父节点设置为根节点即可。路径压缩实际上改变了树的结构，但不会影响并查集的正确性。