Disjoint Set (Union-Find Algorithm) PHP-s

Avaldatud: 16. veebruar 2025, kell 12:25:10 UTC
Viimati uuendatud: 26. jaanuar 2026, kell 10:36:45 UTC

See artikkel tutvustab PHP rakendust Disjoint Set andmestruktuurist, mida tavaliselt kasutatakse Union-Find jaoks minimaalsetes spanning-tree algoritmides.

See lehekülg on inglise keelest masintõlgitud, et muuta see võimalikult paljudele inimestele kättesaadavaks. Kahjuks ei ole masintõlge veel täiuslik tehnoloogia, mistõttu võivad esineda vead. Kui soovite, võite vaadata ingliskeelset originaalversiooni siin:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunktne hulk (tavaliselt kasutatakse Union-Find ehk Disjoint Set Union) on andmestruktuur, mida kasutatakse elementide partitsiooni haldamiseks eraldiseisvateks (mittekattuvateks) hulkadeks. See toetab tõhusalt kahte peamist operatsiooni:

Leia: Määrab, millisesse hulka element kuulub.
Union: Ühendab kaks komplekti kokku.

See struktuur on eriti kasulik minimaalsete spanning tree algoritmides, näiteks Kruskali algoritmis.

Mul on Kruskali algoritmi rakendus, mida kasutatakse juhuslike labürintide genereerimiseks ja mis tugineb alljärgnevale PHP Disjoint Set rakendusele hulkade tõhusaks ühendamiseks. Kui oled huvitatud, saad seda tegevuses näha siin: Kruskali algoritmi labürindi generaator

Igatahes, siin on minu PHP rakendus Disjoint Setist:

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

Lisaks labürintide loomisele lõbu pärast saab Disjoint Seti andmestruktuuri kindlasti kasutada ka päriselu stsenaariumites.

Kujutage näiteks ette sotsiaalvõrgustikku, mis sooviks oma kasutajatele uusi sõpru pakkuda, ja oletame, et meil on juba kuus inimest, kellel on sellised sõprussuhted:

1 ja 2 on sõbrad.
2 ja 3 on sõbrad.
4 ja 5 on sõbrad.
6-l pole sõpru.

Rakendades Union-Find algoritmi nendele eraldiseisvatele rühmadele, peaksime leidma järgmised:

1, 2 ja 3 ühes grupis.
4 ja 5 teise grupi liikmed.
6 kolmandas grupis.

Selle põhjal oleks mõistlik soovitada, et 1 ja 3 võiksid sõpradeks saada, sest neil on ühine isik 2.

Muidugi, väikese näite puhul võiksid selle fakti ise hõlpsasti märgata, kuid selle algoritmi efektiivsus võimaldab tal realistlikult skaleeruda miljardite inimeste ja sõpruskondade seas.