PHP 中的不相交集（並查集演算法）

已發佈: 2025年2月16日中午12:27:46 [UTC]
最後更新： 2026年1月26日上午10:37:01 [UTC]

本文介紹了一個 PHP 實作的 Disjoint Set 資料結構，該結構在最小生成樹演算法中常用於 Union-Find。

該頁面是由英語機器翻譯而來的，以便盡可能多的人可以訪問。不幸的是，機器翻譯還不是一項完善的技術，因此可能會出現錯誤。如果您願意，可以在這裡查看原始英文版本：

Disjoint Set (Union-Find Algorithm) in PHP

不相交集合（Disjoint Set，通常用於 Union-Find，也稱為 Disjoint Set Union）是一種用於管理元素分割成不相交（不重疊）集合的資料結構。它有效支援兩項關鍵操作：

尋找：決定元素屬於哪一組。
Union：將兩組合併在一起。

此結構在最小生成樹演算法中特別有用，例如Kruskal演算法。

我有一個 Kruskal 演算法的實作，用於生成隨機迷宮，它依賴以下 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 資料結構當然也能用於真實情境。

舉例來說，想像一個社群網路想向用戶推薦新朋友，然後假設我們已有六個人擁有這些朋友關係：

1號和2號是朋友。
2號和3號是朋友。
4號和5號是朋友。
6號沒有朋友。

將 Union-Find 演算法應用於這些獨立群，我們應該會得到以下結果：

1、2、3 同組。
第四和第五組在第二組。
第三組有6人。

基於此，建議1號和3號應該成為朋友是合理的，因為他們有共同點2。

當然，在這樣的小例子中，你自己很容易察覺，但這個演算法的效率讓它有可能擴展到數十億人和朋友群。