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

已出版： 2025年2月16日 UTC 12:27:42

本文介绍了不相交集数据结构的 PHP 实现，该结构常用于最小生成树算法中的并查集。

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

Disjoint Set (Union-Find Algorithm) in PHP

不相交集（通常用于并查集，又称不相交集并集）是一种数据结构，用于管理将元素划分为不相交（不重叠）的集合。它有效地支持两个关键操作：

查找：确定元素属于哪个集合。
并集：将两个集合合并在一起。

这种结构在最小生成树算法（例如 Kruskal 算法）中特别有用。

我有一个用于生成随机迷宫的 Kruskal 算法的实现，它依赖于下面的 PHP 实现的 Disjoint Set 来有效地合并集合。如果您感兴趣，可以在此处查看它的实际操作：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。

当然，在像这样的小例子中，你自己很容易就能发现这个事实，但是该算法的效率使其可以扩展到数十亿人和朋友群体。