并查集是一种用于管理元素分组的树形数据结构，支持高效的合并（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_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1
在上面的
union
函数中，
rank
数组用于优化合并操作，它记录了树的高度（或者说是树的深度的一个上界）。通过将高度较低的树连接到高度较高的树上，可以尽量保持树的平衡，避免出现极端情况下树退化成链表的情况。这部分叫做“按秩合并”。
路径压缩： 路径压缩是一种优化查找操作的技巧。在查找过程中，我们将访问过的每个节点直接指向根节点。这样，下次查找这些节点时，就可以直接找到根节点，而不需要沿着路径向上查找。
def find(parent, i): if parent[i] == i: return i parent[i] = find(parent, parent[i]) # 路径压缩 return parent[i]
路径压缩的实现非常简单，只需要在
find
函数中，在递归返回之前，将当前节点的父节点设置为根节点即可。 路径压缩实际上改变了树的结构，但不会影响并查集的正确性。
并查集能解决什么问题？
并查集在很多场景下都有应用，比如：
判断图的连通性： 可以用并查集来判断一个图是否连通，或者计算图中有多少个连通分量。朋友圈问题： 假设每个人都有一些朋友，朋友的朋友也是朋友，可以用并查集来找出有多少个朋友圈。最小生成树算法（Kruskal算法）： Kruskal算法中，需要判断两个节点是否属于同一个集合，这时就可以使用并查集。
并查集的空间复杂度是多少？
并查集的空间复杂度是 O(n)，其中 n 是元素的数量。我们需要一个
parent
数组来存储每个元素的父节点，以及一个
rank
数组（如果使用按秩合并）。
路径压缩会改变树的高度吗？对按秩合并有什么影响？
路径压缩会改变树的高度，使树变得更扁平。但需要注意的是，路径压缩只在查找操作中进行，它并不会更新
rank
数组。这意味着
rank
数组的值可能不再完全准确地反映树的实际高度，但它仍然可以作为树的高度的一个上界，用于指导合并操作，避免树退化成链表。按秩合并与路径压缩结合使用，可以使并查集的性能达到近乎 O(1) 的时间复杂度（均摊）。
以上就是并查集是什么？并查集的路径压缩的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1516948.html
微信扫一扫 
支付宝扫一扫 
