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

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

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

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

Disjoint Set (Union-Find Algorithm) in PHP

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

Намиране: Определя към кой набор принадлежи даден елемент.
Обединение: Обединява две групи заедно.

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

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

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