Disjoint Set (Union-Find Algorithm) PHP

Publicēts: 2025. gada 16. februāris 12:26:08 UTC
Pēdējo reizi atjaunināts: 2026. gada 26. janvāris 10:36:52 UTC

Šajā rakstā ir aprakstīta PHP disjoint set datu struktūras ieviešana, ko parasti izmanto Union-Find minimālajos aptverošos koku algoritmos.

Šī lapa tika mašīntulkota no angļu valodas, lai padarītu to pieejamu pēc iespējas vairāk cilvēkiem. Diemžēl mašīntulkošana vēl nav pilnīga tehnoloģija, tāpēc tajā var rasties kļūdas. Ja vēlaties, oriģinālo versiju angļu valodā varat apskatīt šeit:

Disjoint Set (Union-Find Algorithm) in PHP

Atdalītā kopa (parasti tiek izmantota Union-Find jeb Disjoint Set Union) ir datu struktūra, ko izmanto, lai pārvaldītu elementu sadalījumu nesaistītās (nepārklājošās) kopās. Tas efektīvi atbalsta divas galvenās darbības:

Atrast: nosaka, kurai kopai pieder elements.
Apvienošana. Apvieno divas kopas kopā.

Šī struktūra ir īpaši noderīga minimālo aptverošo koku algoritmos, piemēram, Kruskala algoritmā.

Man ir Kruskala algoritma ieviešana, ko izmanto nejaušu labirintu ģenerēšanai, kas balstās uz zemāk esošo PHP Disjoint Set ieviešanu, lai efektīvi apvienotu kopas. Ja jūs interesē, varat to redzēt darbībā šeit: Kruskal algoritma labirinta ģenerators

Jebkurā gadījumā, šī ir mana PHP Disjoint Set ieviešana:

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

Papildus labirintu ģenerēšanai izklaidei, Disjoint Set datu struktūru noteikti var izmantot arī reālās dzīves scenārijiem.

Iedomājieties, piemēram, sociālo tīklu, kas vēlas ieteikt saviem lietotājiem jaunus draugus, un tad pieņemsim, ka mums ir seši cilvēki ar šīm draugu attiecībām:

1 un 2 ir draugi.
2 un 3 ir draugi.
4 un 5 ir draugi.
6 nav draugu.

Piemērojot Union-Find algoritmu šīm atsevišķajām grupām, mums jāatrod:

1, 2 un 3 vienā grupā.
4 un 5 otrajā grupā.
6 trešajā grupā.

Pamatojoties uz to, būtu lietderīgi ieteikt, ka 1 un 3 vajadzētu kļūt par draugiem, jo viņiem ir kopīga persona 2.

Protams, nelielā piemērā jūs varat viegli pamanīt šo faktu pats, bet šī algoritma efektivitāte ļauj to reāli mērogot miljardiem cilvēku un draugu grupu.