PHP での分離集合 (結合検索アルゴリズム)

出版された： 2025年2月16日 12:25:49 UTC
最終更新日 2026年1月26日 10:36:51 UTC

本記事では、最小スパニングツリーアルゴリズムのユニオン・ファイントによく使われるDisjoint Setデータ構造のPHP実装を紹介します。

このページは、できるだけ多くの人がアクセスできるように、英語から機械翻訳されたものです。残念ながら、機械翻訳はまだ完全な技術ではないため、エラーが発生する可能性があります。もしよろしければ、こちらでオリジナルの英語版をご覧ください：

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set(一般にUnion-Find、別名Disjoint Set Union)は、要素を互いに重ならない集合に分割するためのデータ構造です。効率的に2つの主要な操作をサポートします。

Find:要素がどの集合に属するかを判定します。
ユニオン:2つの集合を統合します。

この構造は特にクルスカルのアルゴリズムのような最小全域木アルゴリズムで有用です。

私は、以下のPHP実装によるDisjoint Setを使って集合を効率的にマージするKruskalアルゴリズムのランダム迷路生成アルゴリズムの実装を持っています。興味があれば、こちらでその動作を見ることができます: クラスカルのアルゴリズム迷路ジェネレータ

とにかく、これが私のPHP実装であるDisjoint Setです:

class DisjointSet 
{
    private $parent = [];
    private $rank   = [];

    public function __construct($size) 
    {
        for ($i = 0; $i < $size; $i++) 
        {
            $this->parent[$i]   = $i;
            $this->rank[$i]     = 0;
        }
    }

    public function find($x) 
    {
        if ($this->parent[$x] != $x) 
        {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }

        return $this->parent[$x];
    }

    public function union($x, $y) 
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX != $rootY) 
        {
            if ($this->rank[$rootX] > $this->rank[$rootY]) 
            {
                $this->parent[$rootY] = $rootX;
            }
            elseif ($this->rank[$rootX] < $this->rank[$rootY]) 
            {
                $this->parent[$rootX] = $rootY;
    
            }
            else
            {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
        }
    }
}

迷路を生成するだけでなく、Disjoint Setデータ構造は実際のシナリオにも十分に活用できます。

例えば、あるソーシャルネットワークがユーザーに新しい友達を提案したいと考え、すでに6人の友人関係を持っているとしましょう:

1番と2番は友達です。
2番目と3番は友達です。
4番と5番は友達です。
6には友達がいません。

これらの別々のグループにUnion-Findアルゴリズムを適用すると、次のようになります。

1、2、3が一つのグループに。
4人と5人、2つ目のグループに。
3つ目のグループに6人。

これを踏まえると、1番と3番は共通点があるので友達になるべきだと示唆するのは理にかなっています。

もちろん、このような小さな例なら自分でも簡単に見分けられますが、このアルゴリズムの効率性により、数十億人や友人グループにも現実的にスケールできます。