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

Опубліковано: 16 лютого 2025 р. о 12:27:35 UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (зазвичай використовується для Union-Find або Disjoint Set 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.

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