网站后台管理系统怎么做,wordpress 如何优化,湖北立方建设工程有限公司网站,国内专业做网站一、概念及其介绍
并查集是一种树型的数据结构#xff0c;用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林#xff08;parent#xff09;#xff0c;树的根节点唯一标识了一个集合#xff0c;我们只要找到了某个元素的的树根#xf…一、概念及其介绍
并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林parent树的根节点唯一标识了一个集合我们只要找到了某个元素的的树根就能确定它在哪个集合里。
二、适用说明
并查集用在一些有 N 个元素的集合应用问题中我们通常是在开始时让每个元素构成一个单元素的集合然后按一定顺序将属于同一组的元素所在的集合合并其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂但数据量极大若用其他的数据结构来描述的话往往在空间上过大计算机无法承受也无法在短时间内计算出结果所以只能用并查集来处理。
三、并查集的基本数据表示 如上图 0-4 下面都是 05-9 下面都是 1表示 0、1、2、3、4 这五个元素是相连接的5、6、7、8、9 这五个元素是相连的。 再如上图 0、2、4、6、8 下面都是 0 这个集合表示 0、2、4、6、8 这五个元素是相连接的1、3、5、7、9 下面都是 1 这个集合表示 01、3、5、7、9 这五个元素是相连的。
构造一个类 UnionFind初始化, 每一个id[i]指向自己, 没有合并的元素
...
public UnionFind1(int n) {count n;id new int[n];// 初始化, 每一个id[i]指向自己, 没有合并的元素for (int i 0; i n; i)id[i] i;}
...
Java 实例代码
UnionFind.java 文件代码
package runoob.union;public class UnionFind{private int[] id;// 数据个数private int count;public UnionFind1(int n) {count n;id new int[n];for (int i 0; i n; i)id[i] i;}}
