Disjoint Set (Union-Find Algorithm) PHP-s

Avaldatud: 16. veebruar 2025, kell 12:25:10 UTC

Selles artiklis käsitletakse disjoint Set andmestruktuuri PHP-rakendust, mida tavaliselt kasutatakse Union-Findi jaoks minimaalse ulatusega puualgoritmides.

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

Disjoint Set (tavaliselt kasutatav Union-Find ehk Disjoint Set Union) on andmestruktuur, mida kasutatakse elementide jaotuse haldamiseks lahknevateks (mittekattuvateks) kogumiteks. See toetab tõhusalt kahte peamist toimingut:

Otsi : määrab, millisesse hulka element kuulub.
Liit : ühendab kaks komplekti kokku.

See struktuur on eriti kasulik minimaalse ulatusega puualgoritmides, nagu Kruskali algoritm.

Mul on juhuslike labürintide genereerimiseks kasutatav Kruskali algoritmi rakendus, mis tugineb komplektide tõhusaks liitmiseks allolevale Disjoint Seti PHP-rakendusele. Kui olete huvitatud, näete seda tegevuses siin: Kruskali algoritmi labürindi generaator

Igatahes, see on minu disjoint Seti PHP-rakendus:

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 lõbu pärast labürintide loomisele saab Disjoint Set andmestruktuuri kindlasti kasutada ka reaalse elu stsenaariumide jaoks.

Kujutage ette näiteks sotsiaalset võrgustikku, mis tahaks oma kasutajatele uusi sõpru soovitada, ja siis oletame, et meil on kuus inimest, kellel on sellised sõbrasuhted juba olemas:

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

Rakendades nendele eraldi rühmadele Union-Find algoritmi, peaksime leidma järgmise:

1, 2 ja 3 ühes rühmas.
4 ja 5 teises rühmas.
6 kolmandas rühmas.

Sellest lähtuvalt oleks mõttekas soovitada 1 ja 3 sõbraks saada, sest neil on isik 2 ühine.

Muidugi võiksite sellise väikese näite puhul seda fakti ise hõlpsasti märgata, kuid selle algoritmi tõhusus võimaldab seda mastaapida miljardite inimeste ja sõbrarühmadeni.