首页 > 代码库 > 并查集的初步认识

并查集的初步认识

首先这个东西是解决什么问题的?什么情况下会用到?

很简单的例子,给出你一个数百万人关系网,随意挑选两个人,问你他们是否有联系?如何快速解决这类问题,这时候需要并查集

并查集意思是说,有个类似指针的东西,将子节点连接父节点,那么这个时候,父子节点是连接的,如果父节点是根节点,那么父节点的指针指向自己;这里让父节点为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
  }
}

 

并查集的初步认识