Disjoint Set (Union-Find Algorithm) PHP

Paskelbta: 2025 m. vasario 16 d. 12:26:02 UTC

Šiame straipsnyje pateikiamas „Disjoint Set“ duomenų struktūros PHP diegimas, dažniausiai naudojamas „Union-Find“ minimalaus apimančio medžio algoritmuose.

Šis puslapis buvo mašininiu būdu išverstas iš anglų kalbos, kad juo galėtų naudotis kuo daugiau žmonių. Deja, mašininis vertimas dar nėra tobula technologija, todėl gali pasitaikyti klaidų. Jei pageidaujate, originalią versiją anglų kalba galite peržiūrėti čia:

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (dažniausiai naudojamas Union-Find, dar žinomas kaip Disjoint Set Union) yra duomenų struktūra, naudojama elementų skaidymui tvarkyti į atskirus (nepersidengiančius) rinkinius. Jis efektyviai palaiko dvi pagrindines operacijas:

Rasti : nustato, kuriam rinkiniui priklauso elementas.
Sąjunga : sujungia du rinkinius.

Ši struktūra ypač naudinga minimalaus apimančio medžio algoritmuose, tokiuose kaip Kruskal algoritmas.

Turiu Kruskal algoritmo, naudojamo atsitiktiniams labirintams generuoti, įgyvendinimą, kuris remiasi toliau pateiktu PHP diegimu Disjoint Set, kad būtų galima efektyviai sujungti rinkinius. Jei susidomėjote, tai galite pamatyti čia: Kruskal algoritmo labirinto generatorius

Bet kokiu atveju, tai yra mano PHP Disjoint Set įgyvendinimas:

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“ duomenų struktūra ne tik sukuria labirintus pramogoms, bet ir gali būti naudojama realaus gyvenimo scenarijuose.

Įsivaizduokite, pavyzdžiui, socialinį tinklą, kuris savo vartotojams norėtų pasiūlyti naujų draugų, o tada tarkime, kad jau turime šešis žmones, turinčius šiuos draugų ryšius:

1 ir 2 yra draugai.
2 ir 3 yra draugai.
4 ir 5 yra draugai.
6 neturi draugų.

Taikydami Sąjungos paieškos algoritmą šioms atskiroms grupėms, turėtume rasti:

1, 2 ir 3 vienoje grupėje.
4 ir 5 antroje grupėje.
6 trečioje grupėje.

Remiantis tuo, būtų prasminga pasiūlyti 1 ir 3 tapti draugais, nes jie turi bendrą 2 asmenį.

Žinoma, tokiame mažame pavyzdyje kaip šis, jūs galite lengvai pastebėti šį faktą patys, tačiau šio algoritmo efektyvumas leidžia jį įgyvendinti milijardams žmonių ir draugų grupių.