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

已發佈: 2025年2月16日中午12:27:46 [UTC]

本文介紹了不相交集資料結構的 PHP 實現，該結構常用於最小生成樹演算法中的並查集。

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

Disjoint Set (Union-Find Algorithm) in PHP

不相交集合（通常用於並查集，稱為不相交集並集）是一種資料結構，用於管理將元素劃分為不相交（不重疊）集合。它有效率地支援兩種關鍵操作：

尋找：確定元素屬於哪個集合。
並集：將兩個集合合併在一起。

這種結構在最小生成樹演算法（例如 Kruskal 演算法）中特別有用。

我有一個用於生成隨機迷宮的 Kruskal 演算法的實現，它依賴於下面的不相交集的 PHP 實現來有效地合併集合。如果你有興趣，可以在這裡看到它的實際效果：Kruskal 演算法迷宮生成器

無論如何，這是我的不相交集的 PHP 實作：

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]++;
            }
        }
    }
}

除了為了好玩而產生迷宮之外，不相交集資料結構當然也可以用於現實生活中的場景。

想像一下，例如，一個社群網路想要向其用戶推薦新朋友，然後假設我們有六個人已經建立了這些朋友關係：

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

將並查集演算法應用到這些單獨的群組，我們應該發現以下內容：

1、2、3為一組。
第二組中的 4 和 5。
第三組有 6 人。

基於此，建議 1 和 3 成為朋友是有道理的，因為他們有共同的人 2。

當然，在像這樣的小例子中，你自己很容易就能發現這個事實，但是該演算法的效率使其可以擴展到數十億人和朋友群體。