【算法基础】并查集的原理及使用
并查集概述
并查集是一种常用的算法,其主要是一种将相关元素放入同一集合的思想。
并查集的使用中主要有两个步骤:合并、查找。
- 合并:将相关元素合并,底层实现主要为数组或哈希表,将相关元素的根结点指向同一节点。
- 查找:查找两个元素是否在同一集合,查找其根结点是否相同即可。
类似于上图中的“门派”划分,在同一门派下即处于相同集合。
并查集优化
1. 路径压缩
减少并查集存储节点时的树形结构的高度,更改节点的指向,减少查找时间
方法一 隔代压缩
原理如下图所示:
实现代码:parent[index] = parent[parent[index]];
方法二 完全压缩
原理如下图所示:
需要利用递归实现。
2. 按秩合并
秩一般代表树的高度。
合并时根据秩,将秩小的树的根结点指向秩大的树的根结点,以避免合并后树的高度增加。
并查集使用
在最小生成树Kruskal方法中可使用并查集。
在部分编程题目比如No.990 LeetCode题目 “等式方程的可满足性”中也可以应用。
参考
本文部分参考: