首页 > 代码库 > 并查集的初步认识
并查集的初步认识
首先这个东西是解决什么问题的?什么情况下会用到?
很简单的例子,给出你一个数百万人关系网,随意挑选两个人,问你他们是否有联系?如何快速解决这类问题,这时候需要并查集
并查集意思是说,有个类似指针的东西,将子节点连接父节点,那么这个时候,父子节点是连接的,如果父节点是根节点,那么父节点的指针指向自己;这里让父节点为A,子节点为B,现在有个新节点C,要让C和B相连,我们只需要让C和B的根节点A相连就可以了;也就是说我们要判断连个点是否相连,只需要判断这两个点的根节点是否一致就行了
下面是代码实现(由于并查集在实现过程有许多优化比范围优化,层级优化,这里上的是优化之后的版本)
class data { constructor (count) { this.p = new Array(count) this.rank = new Array(count) for (let i = 0; i < count; i++) { this.p[i] = i this.rank[i] = 1 // 每个层级初始值为1 } } find (target) { while (target != this.p[target]) { this.p[target] = this.p[this.p[target]] target = this.p[target] } // 递归找出根阶段 return target } isconnect (one, two) { return this.find(one) === this.find(two) } union (one, two) { let Pone = this.find(one), Ptwo = this.find(two) if (Pone === Ptwo) { return } if (this.rank[Pone] < this.rank[Ptwo]) { this.p[Pone] = this.p[Ptwo] } else if (this.rank[Pone] > this.rank[Ptwo]) { this.p[Ptwo] = this.p[Pone] } else { this.p[Ptwo] = this.p[Pone] this.rank[Pone] += 1 } return this.p } }
并查集的初步认识
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。