グラフアルゴリズムの基礎を学ぶーUnionFind

この記事は、グラフアルゴリズムシリーズの3番目の記事です。

1. 概念と表現方法
2. BFSとDFS
3. UnionFind→現在地
4. 最小全域木
5. 単一始点最短経路問題
6. 全点対最短経路問題（WIP）

---

UnionFindとは何か

Union-FindまたはDisjoint Set Union (DSU)とは、グラフ内の任意の2つのノードに対して、直接または間接的に繋がっているかどうかを素早く判断するためのデータ構造・アルゴリズムとなります。グラフは暗黙的に全てのノードが繋がっていると認識してしまうかもしれませんが、実際に連結していないケースもあり得ます。これは連結グラフ・非連結グラフ（connected/disconnected）と呼びます。

このアルゴリズムには、2つの中心的関数・メソッドが存在します。

• find 任意のノードのルートノードを探し出す
• union 任意の2つのノードのルートノードを同じノードにする（直接または間接的に繋げる）

ルートノードはその名前通り、親ノードのないノードとなります。

例えば、下記のグラフを例にすると、ノードEのルートノードはE自身、FのルートノードはD、BとCのルートノードはA（B->A->Cでも良いが、後で紹介するオプティマイズ方法によって基本Aがルートになる）という感じです。

UnionFindは、AとEが繋いでいるかどうか、BとFが繋いでいるかどうかを効率よく判断するために、find(a) == find(b)で結論がわかります。これは通常、connectedメソッドとして実装されます。

UnionFindは実際のコード上では、よく配列として表現されています。ただ、直感と相反するかもしれませんが、配列のインデックスがノードとなっており、値が頂点のルートノードを表しているのです。初期状態では、配列の各値が、該当ノード（インデックス）の親ノードとなっているため、unionやfindの関数を通して、親ノードの親ノードを探し続けて、最終的にルートノードのインデックスを値に更新することです。

次にUnionFindの実装について説明します。

実装

Quick Find

この実装では、名前通り、findメソッドを一番効率よくすることができます。時間複雑度O(1)の、配列ランダムアクセスとなります。

class UnionFind {
  constructor(size) {
    this.root = [...Array(size).keys()];
  }

  find(x) {
    return this.root[x]; // ここがquick find
  }

  union(x, y) {
    // まずはそれぞれのルートノードを探し出す
    const rootX = this.find(x);
    const rootY = this.find(y);
    // 一致しない場合のみ、連結操作を行う
    if (rootX !== rootY) {
      // 全てのルートノードをループし、ルートノードの値がyだったものをxに入れ替える（逆もOK）
      for (const [i, value] of this.root.entries()) {
        if (value === rootY) {
          this.root[i] = rootX;
        }
      }
    }
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

時間複雑度は以下となります（n=ノードの数）。

constructor	find	union	connected
O(n)	O(1)	O(n)	O(1)

Quick Union

class UnionFind {
  constructor(size) {
    this.root = [...Array(size).keys()];
  }

  find(x) {
    while (x !== this.root[x]) {
      x = this.root[x];
    }
    return x;
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      this.root[rootY] = rootX;
    }
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

時間複雑度は以下となります（n=ノードの数）。

constructor	find	union	connected
O(n)	O(n)	O(n)	O(n)

一見、quick findより複雑度が高いように見えますが、実際にquick unionの方がほとんどの場合、効率がよくなります。理由というのは、

• quick findのunionメソッドでは、二つのノードを繋げるたびに、配列を一回ループしています。これは変動する値ではなく、固定でO(n)となっているのです。
• quick unionのfindメソッドでは、最悪ケース＝連結リストになっているケースのみ、複雑度がO(n)になります。つまり、findの複雑度は事実上、<=O(n)となるはずです。
• 固定のO(n)と比べて、<=O(n)の方が効率良いというわけです。

最適化

Quick Unionの実装ではすでに効率の良い実装になっているのではないか、と思うかもしれませんが、ここで2つ最適化の方法を紹介します。

Unionのランク付

今までのunionメソッドの実装には一つ欠点があります。それは、ルートノードの入れ替えの際に、明確な基準がなく、一律xまたはyのルートノードに入れ替えているだけとのところです。

これで何が問題になるかというと、極端な場合、ノードを全部連結した結果、連結リストになってしまい、findが最悪ケースになってしまうことです。例えば、union(4, 5) -> union(3, 4) -> union(2, 3) ...の順で連結すると、下記の一直線になってしまいます。

この問題を避けるために、やはりどのノードのルートノード値を優先にするか、を判断する基準を作る必要があります。これは、ランク付の目的となります。

class UnionFind {
  constructor(size) {
    this.root = [...Array(size).keys()];
    this.rank = Array(size).fill(1); // 初期値は1でも0でも構いません
  }

  find(x) {
    while (x !== this.root[x]) {
      x = this.root[x];
    }
    return x;
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      // ルートノードの値を用いて、ランク配列からランクを取得して比較する
      if (this.rank[rootX] > this.rank[rootY]) {
        this.root[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.root[rootX] = rootY;
      } else {
        this.root[rootY] = rootX;
        this.rank[rootX] += 1; // ランクが一緒の場合、入れ替える方に+1
      }
    }
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

ここでランクを表す配列を導入し、ルートノードをインデックスとして、ランクを値にします。unionする度に、このランクに基づいて判断すると、先ほどの極端なケースは発生しなくなります。

Path Compression

今までのfindメソッドでは、whileループを使って、親ノード→親ノード→...→ルートノードの形で探索しています。これを極端に最適化すると、間接的に繋いでいるノードを無くし、全てルートノードと直接繋げることができれば、探索が->ルートノードの一発で終わるはずですね。これは、経路圧縮（path compression）のことです。

class UnionFind {
  constructor(size) {
    this.root = [...Array(size).keys()];
    this.rank = Array(size).fill(1);
  }

  find(x) {
    // x === this.root[x]となると、xポジションにある値はすでにルートノード
    if (x !== this.root[x]) { 
      // 再帰の呼び出しを通して、D -> C -> B -> Aの経路上のD, C, Bのルートノードを全部Aにする
      this.root[x] = this.find(this.root[x]); 
    }
    // この時点で経路上にある全てのノードのルートノードは入れ替えられたので、this.root[x]で十分
    return this.root[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      // ルートノードの値を用いて、ランク配列からランクを取得して比較する
      if (this.rank[rootX] > this.rank[rootY]) {
        this.root[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.root[rootX] = rootY;
      } else {
        this.root[rootY] = rootX;
        this.rank[rootX] += 1; // ランクが一緒の場合、入れ替える方に+1
      }
    }
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

時間複雑度は以下となります（n=ノードの数）。

constructor	find	union	connected
O(n)	O(α(n))	O(α(n))	O(α(n))

アルファはInverse Ackermann関数のことを指しています。定数と考えて良いので、平均的にO(α(n))=O(1)と扱うことができます（説明はこちら）。

これでようやく、最適化されたUnionFindが見えてきました。他にもテクニックがありますが、次の実践問題の中で見てみようと思います。

実践問題

Leetcodeの問題547. Number of Provincesを見てみます。

この問題は典型的なUnionFindとなります。グラフをビルドするために、まずは2回のループを通して繋いでいるノードに対してunion操作を行います。ここでcountを導入して、繋いでいない島の数を表します。unionのプロセスが終われば、countがその結果となります。

class UnionFind {
  constructor(size) {
    this.root = [...Array(size).keys()];
    this.rank = Array(size).fill(1);
    // countは繋いでいない島の数を表している→初期状態では全部のノードが繋いでいないのでsizeと同じ
    this.count = size;
  }

  find(val) {
    if (this.root[val] !== val) {
      this.root[val] = this.find(this.root[val]);
    }
    return this.root[val];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.root[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.root[rootX] = rootY;
      } else {
        this.root[rootY] = rootX;
        this.rank[rootX] += 1;
      }
      this.count -= 1; // ノードをつなぐ度にカウントを-1
    }
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const dsu = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) {
        dsu.union(i, j);
      }
    }
  }
  return dsu.count; // 残っているカウント数は繋いでいない島の数になる
}

UnionFindは後程のMST関連のアルゴリズムにも運用できるので、一旦これで問題例を終わりにします。他にもこれらの問題があるので、興味があれば解いてみてください。

• 261. Graph Valid Tree
• 399. Evaluate Division
• 1101. The Earliest Moment When Everyone Become Friends
• 1202. Smallest String With Swaps
• 1168. Optimize Water Distribution in a Village

終わりに

今回はUnionFindについて紹介しました。次は最小全域木について書きます。