大企业网站建设公司,火车头 wordpress 发布,域名年龄对seo的影响,足球比赛直播中国队目录 并查集的定义并查集的基本操作初始化查找合并 路径压缩 并查集的定义
并查集是一种维护集合的数据结构#xff0c;支持下面两个操作#xff1a;
合并#xff1a;合并两个集合。查找#xff1a;判断两个元素是否在一个集合。
并查集用一个数组实现#xff1a;
int… 目录 并查集的定义并查集的基本操作初始化查找合并 路径压缩 并查集的定义
并查集是一种维护集合的数据结构支持下面两个操作
合并合并两个集合。查找判断两个元素是否在一个集合。
并查集用一个数组实现
int father[N];father[i]表示元素i的父亲结点而父亲结点本身也是这个集合内的元素(1 ≤ i ≤ N)。如果father[i] i则说明元素i是该集合的根结点。对同一个集合来说只存在一个根结点且将其作为所属集合的标识。
并查集的基本操作
初始化
一开始每个元素都是独立的一个集合因此需要令所有father[i]等于i()
for (int i 1; i N; i)father[i] i;查找
对给定结点寻找其根结点即father[i] i的结点的过程。
递推代码
// findFather函数返回元素x所在集合的根结点
int findFather(int x) {while (x ! father[x]) // 如果不是根结点,继续循环x father[x]; // 获得自己的父亲结点return x;
}递归代码
int findFather(int x) {if (x father[x])return x;elsereturn findFather(father[x]);
}合并
对于给定的两个元素a、b判断它们是否属于同一集合。可以调用上面的查找函数对这两个元素a、b分别查找根结点然后再判断其根结点是否相同。合并两个集合在①中已经获得了两个元素的根结点faA和faB因此只需要把其中一个的父亲结点指向另一个结点即可。如令father[faA] faB。在合并过程中只对两个不同集合进行合并如果两个元素在相同的集合中则不进行合并操作。这样保证了在同一个集合中一定不会产生环即并查集产生的每个集合都是一棵树。
void Union(int a, int b) {int faA findFather(a); // 查找a的根结点,记为faAint faB findFather(b); // 查找b的根结点,记为faBif (faA ! faB) // 如果不属于同一个集合father[faA] faB; // 合并它们
}路径压缩
把当前查询结点的路径上的所有结点的父亲都指向根结点查找的时候就不需要一直回溯去找父亲了查询的复杂度可以降为O(1)。
按原先的写法获得x的根结点r。重新从x开始走一遍寻找根结点的过程把路径上经过的所有结点的父亲全部改为根结点r。
递推版本
int findFather(int x) {int a x; // 保存原先的xwhile (x ! father[x]) // 寻找x的根结点x father[x]; // 循环结束后,x存放的是根节点// 下面把路径上的所有结点的father都改为根结点while (a ! father[a]) {int z a; // 保存原先的aa father[a]; // a回溯父亲结点father[z] x; // 将原先的结点a的父亲改为根结点x}return x; // 返回根结点
}递归版本
int findFather(int x) {if (x father[x]) // 找到根结点return x;else {int r findFather(father[x]); // 递归寻找father[x]的根结点rfather[x] r; // 将根结点r赋值给father[x]return r; // 返回根结点r}
}或者
int findFather(int x) {if (x ! father[x]) // x不是根结点father[x] findFather(father[x]); // 找到x父亲结点根结点,并做路径压缩return father[x]; // 返回根结点
}
