Диз'єднана множина (алгоритм union-find) в PHP

Опубліковано: 16 лютого 2025 р. о 12:27:35 UTC
Останнє оновлення: 26 січня 2026 р. о 10:36:59 UTC

У цій статті представлено PHP-реалізацію структури даних Disjoint Set, яка часто використовується для пошуку Union-Find в алгоритмах мінімального остовного дерева.

Ця сторінка була перекладена з англійської мови машинним перекладом, щоб зробити її доступною для якомога більшої кількості людей. На жаль, машинний переклад ще не є досконалою технологією, тому можуть траплятися помилки. Якщо ви бажаєте, ви можете переглянути оригінальну англійську версію тут:

Disjoint Set (Union-Find Algorithm) in PHP

Неперетинна множина (зазвичай використовується для Union-Find, також відомого як Ununited Set Set) — це структура даних, яка використовується для керування розбиттям елементів на неперетинаючі (не перекриваючись) множини. Вона ефективно підтримує дві ключові операції:

Find: Визначає, до якої множини належить елемент.
Union: об'єднує два набори разом.

Ця структура особливо корисна в алгоритмах мінімального остовного дерева, таких як алгоритм Крускаля.

У мене є реалізація алгоритму Крускаля, яка використовується для генерації випадкових лабіринтів і базується на наведеній нижче 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.

Звісно, у такому невеликому прикладі ви можете легко помітити цей факт самі, але ефективність цього алгоритму дозволяє йому масштабуватися до мільярдів людей і груп друзів.