Непересекающийся набор (алгоритм объединения-поиска) в PHP

Опубликовано: 16 февраля 2025 г. в 12:26:57 UTC
Последнее обновление: 26 января 2026 г. в 10:36:57 UTC

В этой статье представлена PHP-реализация структуры данных Disjoint Set, которая обычно используется для объединения в алгоритмах минимального остовного дерева.

Эта страница была переведена с английского языка для того, чтобы сделать ее доступной как можно большему числу людей. К сожалению, машинный перевод еще не является совершенной технологией, поэтому возможны ошибки. Если вы хотите, вы можете просмотреть оригинальную английскую версию здесь:

Disjoint Set (Union-Find Algorithm) in PHP

Непересекающееся множество (широко используемое для Union-Find, также известного как объединение непересекающихся множеств) — это структура данных, используемая для управления разбиением элементов на непересекающиеся (непересекающиеся) множества. Он эффективно поддерживает две ключевые операции:

Find: Определяет, к какому множеству принадлежит элемент.
Союз: объединяет два комплекта.

Эта структура особенно полезна в алгоритмах минимального остона, таких как алгоритм Крускаля.

У меня есть реализация алгоритма Крускаля, используемая для генерации случайных лабиринтов, которая основана на приведённой ниже PHP-реализации Disjoint Set для эффективного объединения множеств. Если вам интересно, вы можете увидеть это в действии здесь: Генератор лабиринтов по алгоритму Крускала

В любом случае, вот моя 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.

Конечно, в таком небольшом примере вы легко можете заметить этот факт сами, но эффективность этого алгоритма позволяет реализовать масштабирование до миллиардов людей и групп друзей.