Disjoint Set (Union-Find Algorithm) во PHP

Објавено: 5 март 2025, во 19:55:26 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.

Се разбира, во мал пример како овој, лесно можете сами да го забележите овој факт, но ефикасноста на овој алгоритам овозможува тој изводливо да се размери на милијарди луѓе и групи пријатели.