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

Објављено: 16. фебруар 2025. 12:34:17 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.

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