Disjoint Set (алгоритъм за намиране на съюз) в PHP

Публикувано: 16 февруари 2025 г. в 12:20:19 ч. UTC
Последна актуализация: 26 януари 2026 г. в 10:36:41 ч. UTC

Тази статия представя PHP имплементация на структурата от данни Disjoint Set, която често се използва за Union-Find в алгоритми с минимално разширено дърво.

Тази страница е машинно преведена от английски език, за да бъде достъпна за възможно най-много хора. За съжаление машинният превод все още не е съвършена технология, така че могат да възникнат грешки. Ако предпочитате, можете да видите оригиналната версия на английски език тук:

Disjoint Set (Union-Find Algorithm) in PHP

Несъвпадащото множество (често използвано за Union-Find, известен още като Unjoint Set Union) е структура от данни, използвана за управление на разделяне на елементи в несъвместими (неприпокриващи се) множества. Той поддържа ефективно две ключови операции:

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

Тази структура е особено полезна при алгоритми с минимално обхващащо дърво, като алгоритъма на Крускал.

Имам имплементация на алгоритъма на Крускал, използвана за генериране на случайни лабиринти, която разчита на по-долу 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.

Разбира се, в малък пример като този, лесно бихте могли сами да забележите този факт, но ефективността на този алгоритъм му позволява реалистично да се мащабира до милиарди хора и приятелски групи.