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

已出版： 2025年2月16日 UTC 12:27:42
最后更新 2026年1月26日 UTC 10:37:00

本文介绍了一个 PHP 实现的 Disjoint Set 数据结构，该结构在最小生成树算法中常用于 Union-Find。

为了使尽可能多的人能够访问本页面，本页面由英文机译而成。遗憾的是，机器翻译技术尚不完善，因此可能会出现错误。如果您愿意，可以在此处查看原始英文版本：

Disjoint Set (Union-Find Algorithm) in PHP

不相交集（通常用于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同组。
第二组是4和5。
第三组有6个。

基于此，建议1号和3号应该成为朋友是合理的，因为他们有共同点2。

当然，在这样的小例子中，你自己也能轻易察觉，但该算法的高效性使其能够可行地扩展到数十亿人和朋友群体。