Дисјунктни скуп (Алгоритам Унион-Финд) у ПХП-у

Објављено: 16. фебруар 2025. 12:34:17 UTC
Последње ажурирано: 26. јануар 2026. 10:37:16 UTC

Овај чланак садржи ПХП имплементацију Дисјоинт Сет структуре података, која се обично користи за Унион-Финд у минималним алгоритмима стабла.

Ова страница је машински преведена са енглеског како би била доступна што већем броју људи. Нажалост, машинско превођење још увек није усавршена технологија, тако да може доћи до грешака. Ако желите, можете погледати оригиналну енглеску верзију овде:

Disjoint Set (Union-Find Algorithm) in PHP

Дисјунктни скуп (обично се користи за Унион-Финд ака Дисјоинт Сет Унион) је структура података која се користи за управљање поделом елемената у дисјунктне (не-преклапајуће) скупове. Ефикасно подржава две кључне операције:

Пронађи : Одређује којем скупу елемент припада.
Унија : Спаја два сета заједно.

Ова структура је посебно корисна у алгоритмима минималног обухвата стабла, као што је Крускалов алгоритам.

Имам имплементацију Крускаловог алгоритма који се користи за генерисање случајних лавиринта који се ослања на доњу ПХП имплементацију Дисјоинт Сет-а за ефикасно спајање скупова. Ако сте заинтересовани, можете га видети у акцији овде: Крускалов алгоритам Мазе Генератор

У сваком случају, ово је мој ПХП имплементација Дисјоинт Сет:

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]++;
            }
        }
    }
}

Осим генерисања лавиринта за забаву, структура података Дисјоинт Сет свакако се може користити и за сценарије из стварног живота.

Замислите , на пример, друштвену мрежу која би желела да предложи нове пријатеље својим корисницима, а онда рецимо да имамо шест људи са овим пријатељским односима који су већ на месту:

1 и 2 су пријатељи.
2 и 3 су пријатељи.
4 и 5 су пријатељи.
6 нема пријатеља.

Применом алгоритма Унион-Финд на ове одвојене групе, требало би да нађемо следеће:

1 , 2 и 3 у једној групи.
4 и 5 у другој групи.
6 у трећој групи.

На основу тога, имало би смисла предложити да 1 и 3 постану пријатељи, јер имају заједничку особу 2.

Наравно , у малом примеру као што је овај, лако бисте могли сами уочити ову чињеницу, али ефикасност овог алгоритма омогућава му да се изводљиво скалира на милијарде људи и група пријатеља.