1: 动态连通性
可以检测所给的点中 是否有环的:
概念:
- 并查集:(union-find sets)
一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。
- 并查集的精髓(即它的三种操作,结合实现代码模板进行理解):
1、Make_Set(x) 把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身(也可以根据情况而变)。
2、Find_Set(x) 查找一个元素所在的集合
查找一个元素所在的集合,其精髓是找到这个元素所在集合的祖先!这个才是并查集判断和合并的最终依据。
判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
合并两个集合,也是使一个集合的祖先成为另一个集合的祖先,具体见示意图
3、Union(x,y) 合并x,y所在的两个集合
合并两个不相交集合操作很简单:
利用Find_Set找到其中两个集合的祖先,将一个集合的祖先指向另一个集合的祖先。如图
- 并查集的优化
1、Find_Set(x)时 路径压缩
寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示;可见,路径压缩方便了以后的查找。
2、Union(x,y)时 按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
package com.algorithm.common.tree; import com.algorithm.lib.StdOut; /** * 动态连通性检查 (并查集算法) * @author lijunqing */ public class UF { /** * i节点的父节点(集合) */ private int[] id; // id[i] = parent of i /** * i集合中子节点数量 */ private int[] sz; // sz[i] = number of objects in subtree rooted at i /** * 集合总数 */ private int count; // number of components /** * 初始化N个集合 */ public UF(int N) { // n表示所有数值就是count if(N < 0) throw new IllegalArgumentException(); count=N; id=new int[N]; sz=new int[N]; for(int i=0; i < N; i++) { id[i]=i; sz[i]=1; } } /** * 查找一个元素所在的集合(其精髓是找到这个元素所在集合的祖先) 就是找到改元素所在集合的祖先 */ public int find(int p) { if(p < 0 || p >= id.length) throw new IndexOutOfBoundsException(); while(p != id[p]) //// 相等表示找到祖先 p=id[p]; return p; } /** * 返回集合总数 */ public int count() { return count; } /** * 判断pq是否在同一集合中 */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * 合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小 */ public void union(int p, int q) { int i=find(p); int j=find(q); if(i == j) return; // make smaller root point to larger one if(sz[i] < sz[j]) { // 元素少的集合合并到元素多的集合中 id[i]=j; // i的父节点是j sz[j]+=sz[i]; } else { id[j]=i; // j的父节点是i sz[i]+=sz[j]; // 改变父节点的值(值越大表示其子节点越多) } count--; } public static void main(String[] args) { int N=10; UF uf=new UF(N); uf.union(1, 2); uf.union(3, 4); uf.union(6, 7); uf.union(2, 7); int a=uf.find(6); System.out.println(a); StdOut.println(uf.count() + " components"); } }
其中id保存:
0 1 1 3 3 5 1 6 8 9
相关推荐
但是实际上有着更高效的数据结构来判断节点间是否具有连通性,那就是并查集接口并查集这一数据结构由数组构建而成,使用数组下标来表示具体的节点,使用数组保存的值来表示
图论- 图的连通性- 并查集判断连通性.rar
带权并查集(Weighted Union-Find)是一种在数据结构中用于处理不相交集合(Disjoint Set)的算法,它通过合并过程来减少集合的数量,同时考虑合并操作的权重。以下是一个针对带权并查集模板的资源描述: 资源标题...
并查集(Disjoint Set)是一种用于处理集合合并和查询连通性的数据结构。它主要支持以下两种操作: MakeSet(x): 创建一个新的集合,其中包含元素x,并将其作为单独的集合。 Find(x): 查找元素x所属的集合的代表元素...
利用散列表解决检查网络连通性问题。此问题较为简便
本课件主要讲解了并查集,割点和桥,强连通分量(Kosaraju, Tarjan)
并查集算法,主要是解决图论中「动态连通性」问题的 Union-Find 算法解决的是图的动态连通性问题,这个算法本身不难,能不能应用出来主要是看你抽象问题的能力,是否能够把原始问题抽象成一个有关图论的问题。 如果...
掌握并查集的基本原理和应用,通过父亲数组father、查找find()、合并join()实现并查集,以确定图的连通性。同时也了解到通过路径压缩和按秩合并的并查集优化方法。路径压缩在图规模较大、树深度较大时效果会比较好。
前言用于解决动态连通性问题,能动态连接两个点,并且判断两个点是否连通。public abstract class UF {protected int[] id;
前言用于解决动态连通性问题,能动态连接两个点,并且判断两个点是否连通。public abstract class UF {protected int[] id;
(2) 并查集的基本原理和应用。 找出一个无向图中所有的桥 数据获取 边稀疏 空间浪费 基准算法 深度优先dfs 查并集dsu 高效算法 dfs基准算法优化(判断可达) 查并集+最小公共祖先 数据处理 基准算法:DFS比...
并查集扩展(friend_enemy) 堆(binary) 堆(mapped) 矩形切割 线段树 线段树扩展 线段树应用 子段和 子阵和 其他\ 大数(整数类封装) 分数 矩阵 线性方程组(gauss) 日期 线性相关 数论\ 阶乘最后非零位...
并查集可以动态地连通两个点,并且可以非常快速地判断两个点是否连通。 6 位运算 7 双指针 8 排序 堆排序/快速排序 桶排序 荷兰国旗 9 贪心思想 保证每次操作都是局部最优的,并且最后得到的结果是全局最优的。 10 ...
经典问题整理 基础问题 二叉树的遍历 二叉搜索树 ...连通性/并查集 弗洛伊德 迪克斯特拉 数学 冷门问题 随机化 蓄水池采样 拒绝采样法 概率分布 洗牌算法 计算几何 凸包 最近点对 图论 经理 高斯消元
并查集数据结构:并查集是一种用于处理不相交集合的数据结构,支持合并和查找操作,用于解决集合合并、连通性问题等。 AVL树数据结构:AVL树是一种自平衡的二叉查找树,通过维护节点的平衡因子来保持树的平衡,实现...
1 5 5 并查集 16 1 6 技术 18 1 6 1 比较 18 1 6 2 排序 18 1 6 3 扫描 19 1 6 4 贪婪算法 20 1 6 5 动态规划算法 20 1 6 6 用整数编码集合 21 1 6 7 二分查找 23 1 7 建议 25 1 8 走得更远 27 第 2 章 字符串 28 2 ...
并查集 路径压缩思想的应用 STL中的数据结构 vector deque set / map 动态规划 / 记忆化搜索 动态规划和记忆化搜索在思考方式上的区别 最长子序列系列问题 最长不下降子序列 最长公共子序列 一类NP...
许智磊 -《浅谈补集转化思想在统计问题中的应用》 张 宁 -《猜数问题的研究》 张云亮 -《论对算法的选择》 周 源 -《浅析"最小表示法"思想在字符串循环同构问题中的应用》 ## 2004 何 林 -《信息学中守恒法...
此资源内容为大学生课程设计的题目,实现的功能为对于给定图的判断是否存在欧拉路径,使用的编程语言为Java,采用邻接表作为图的存储结构,使用并查集判断图的连通性,基于深度优先算法,广度优先算法,佛洛莱算法...
6.5.4 并查集 第7章 数组和矩阵 7.1 数组 7.1.1 抽象数据类型 7.1.2 C++数组的索引 7.1.3 行主映射和列主映射 7.1.4 用数组的数组来描述 7.1.5 行主描述和列主描述 7.1.6 不规则二维数组 7.2 矩阵 7.2.1 定义和操作 ...