当前位置：首页 > news >正文

并查集结构

news 2025/8/18 7:39:45

文章目录

并查集特点
构建过程
- 查找两个元素是否是同一集合
- - 优化查找领头元素
- 设置两个元素为同一集合
构建结构
应用场景
- 并行计算集合问题

并查集特点

对于使用并查集构建的结构，可以使得查询两个元素是否在同一集合，以及合并集合的操作无限接近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);}}}
}