【TypeScript】繋がっているかどうか判定『Union Find』

やりたいこと

繋がっているかどうか判定したいことがあります。

この図を見てください。

1と7は繋がっています。
1と8は繋がっていないです。

ここで、○○と××は繋がっているかを高速に判定できるアルゴリズムがほしいです。

問題点

全ての接続情報を持とうとすると頂点の二乗のメモリが必要です。
更に、その情報を構築するのに頂点の三乗回計算しないといけないです。

解決策

Union Findというアルゴリズムがあります。
Disjoint Setとも言います。

必要なメモリの量は頂点の数
計算量は

• 構築に線の数よりちょっとだけ多い
• 判定は1回よりちょっとだけ多い

です。

コード

class UnionFind {
  private parents: number[];

  public constructor(private n: number) {
    this.parents = new Array<number>(n);
    for (let i = 0; i < n; i++) this.parents[i] = -1;
  }

  public root(a: number): number {
    if (this.parents[a] < 0) {
      return a;
    }
    return (this.parents[a] = this.root(this.parents[a]));
  }

  public size(a: number): number {
    return -this.parents[this.root(a)];
  }

  public connect(a: number, b: number): boolean {
    let ra = this.root(a);
    let rb = this.root(b);
    if (ra === rb) {
      return false;
    }

    if (this.size(ra) < this.size(rb)) {
      const tmp = ra;
      ra = rb;
      rb = tmp;
    }
    this.parents[ra] += this.parents[rb];
    this.parents[rb] = ra;
    return true;
  }

  public isUnion(a: number, b: number): boolean {
    const ra = this.root(a);
    const rb = this.root(b);
    return ra === rb;
  }
}

function main() {
  const uf = new UnionFind(12);
  uf.connect(0, 1);
  uf.connect(1, 2);
  uf.connect(2, 3);
  uf.connect(3, 4);
  uf.connect(3, 5);
  uf.connect(3, 6);
  uf.connect(6, 7);
  uf.connect(8, 9);
  uf.connect(8, 10);
  uf.connect(10, 11);

  console.log(`1と7は繋がっているか？ :${uf.isUnion(1, 7)}`);
  console.log(`1と8は繋がっているか？ :${uf.isUnion(1, 8)}`);
  console.log(`1と繋がっているのは何個か？ :${uf.size(1)}`);
  console.log(`8と繋がっているのは何個か？ :${uf.size(8)}`);
}

main();

1と7は繋がっているか？ :true
1と8は繋がっているか？ :false
1と繋がっているのは何個か？ :8
8と繋がっているのは何個か？ :4