Disjoint Set (Union-Find Algorithm) PHP

Paskelbta: 2025 m. vasario 16 d. 12:26:02 UTC
Paskutinį kartą atnaujinta: 2026 m. sausio 26 d. 10:36:52 UTC

Šiame straipsnyje pateikiamas PHP disjoint set duomenų struktūros įgyvendinimas, dažniausiai naudojamas Union-Find minimalaus aprėpianč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

Atskiras rinkinys (paprastai naudojamas Union-Find, dar žinomas kaip Disjoint Set Union) yra duomenų struktūra, naudojama elementų padalijimui į atskirus (nepersidengiančius) rinkinius valdyti. Jis efektyviai palaiko dvi pagrindines operacijas:

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

Ši struktūra ypač naudinga minimalaus aprėpties medžio algoritmuose, tokiuose kaip Kruskala algoritmas.

Turiu įgyvendinti Kruskal algoritmą, naudojamą atsitiktinių labirintų generavimui, kuris remiasi žemiau pateiktu PHP įgyvendinimu Disjoint Set efektyviai sujungti rinkinius. Jei jus domina, galite pamatyti jį veikiant čia: Kruskal algoritmo labirinto generatorius

Bet kokiu atveju, tai yra mano PHP įgyvendinimas 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]++;
            }
        }
    }
}

Be labirintų kūrimo pramogai, "Disjoint Set" duomenų struktūra tikrai gali būti naudojama ir realiems scenarijams.

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

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

Taikydami "Union-Find" 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, kad 1 ir 3 turėtų tapti draugais, nes jie turi bendrą asmenį 2.

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