长沙哪里学网站建设,黑河做网站哪家好,网站建设注意事项 南京,网站开发毕设参考文献文章目录并查集特点构建过程查找两个元素是否是同一集合优化查找领头元素设置两个元素为同一集合构建结构应用场景并行计算集合问题并查集特点
对于使用并查集构建的结构#xff0c;可以使得查询两个元素是否在同一集合#xff0c;以及合并集合的操作无限接近O(1)
构建过程…
文章目录并查集特点构建过程查找两个元素是否是同一集合优化查找领头元素设置两个元素为同一集合构建结构应用场景并行计算集合问题并查集特点
对于使用并查集构建的结构可以使得查询两个元素是否在同一集合以及合并集合的操作无限接近O(1)
构建过程
查找两个元素是否是同一集合
并查集结构会让每个元素合并后挂在一个领头元素上可能呈现下面的结构要判断d和f是否是同一集合就判断顶部的零头元素是否一样因为a和e不一样所以不是同一集合 优化查找领头元素
如上图的结构当要查找d的领头元素时需要一直往上遍历当节点深度很深时也会带来负担优化方式是当某个元素查找到领头元素后将元素路径上所经过的所有节点的领头元素设置成查找的节点比如d查找到a后将b的领头元素设置成a通过上面的优化手段可以看出当使用并查集查询查询领头元素的次数越多查找的效率就越好
设置两个元素为同一集合
将两个元素的领头元素设置成同一个即可即将挂载节点少的领头元素挂载到挂载节点多的领头元素下比如上图将e挂载到a下因为查找元素是否在同一集合是根据领头元素是否相同来的
构建结构
class Element {value;constructor(value) {this.value value;}
}class Union {// 给定元素对应的修饰对象elementMap;// 元素对应的父元素fatherMap;// 领头元素下挂载的元素个数sizeMap;constructor(list) {this.elementMap new Map();this.fatherMap new Map();this.sizeMap new Map();list.forEach((value) {const element new Element(value);this.elementMap.set(value, element);// 初始将所有元素都领头元素设置成自身this.fatherMap.set(element, element);// 初始所有领头元素下挂载的元素个数为1this.sizeMap.set(element, 1);});}// 查找领头元素findHead(element) {const path [];// 找到领头元素while (element ! this.fatherMap.get(element)) {path.push(element);element this.fatherMap.get(element);}// 优化操作将路径上的元素的父元素都更新成领头元素while (path.length) {this.fatherMap.set(path.pop(), element);}return element;}// 判断是否同一集合isSameSet(value1, value2) {if (this.elementMap.has(value1) this.elementMap.has(value2)) {return (this.findHead(this.elementMap.get(value1)) this.findHead(this.elementMap.get(value2)));}return false;}// 设置两个元素为同一集合setUnion(value1, value2) {if (this.elementMap.has(value1) this.elementMap.has(value2)) {const head1 this.findHead(this.elementMap.get(value1));const head2 this.findHead(this.elementMap.get(value2));if (head1 ! head2) {const bigOne this.sizeMap(head1) this.sizeMap(head2) ? head1 : head2;const smallOne bigOne head1 ? head2 : head1;this.fatherMap.set(smallOne, bigOne);this.sizeMap.set(bigOne,this.sizeMap.get(bigOne) this.sizeMap.get(smallOne));this.sizeMap.delete(smallOne);}}}
}
应用场景
并行计算集合问题
初始问题和解法 通过多线程计算将整个内容分成左右两个区域通过多线程分别求出左右两个面积的岛屿数量为1个和2个总和为3但实际岛屿答案为2个所以还要计算左右两个是否有岛屿是属于同一个集合
首先判断每一行分割的位置左右相邻节点是否都为1是1说明为同一集合通过并查集设置为同一集合将总岛屿数量-1同理后续相邻1节点只需要先通过并查集结构判断是否在同一集合如果没有则设置为同一集合然后岛屿数量-1的操作即可因为查询和合并的代价都很低所以再通过多线程带来的提速更快了
