Disjoint Set (Union-Find Algorithm) PHP

Publicēts: 2025. gada 16. februāris 12:26:08 UTC

Šajā rakstā ir ietverta PHP implementācija Disjoint Set datu struktūrai, ko parasti izmanto Union-Find minimālo aptverošo 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

Disjoint Set (ko parasti izmanto Union-Find jeb Disjoint Set Union) ir datu struktūra, ko izmanto, lai pārvaldītu elementu nodalījumu nesadalītās (nepārklājas) kopās. Tas efektīvi atbalsta divas galvenās darbības:

Find : nosaka, kurai kopai pieder elements.
Savienība : apvieno divas kopas.

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

Man ir Kruskal algoritma implementācija, ko izmanto nejaušu labirintu ģenerēšanai, kas balstās uz tālāk norādīto PHP Disjoint Set implementāciju, lai efektīvi apvienotu kopas. Ja jūs interesē, jūs varat redzēt to darbībā šeit: Kruskal algoritma labirinta ģenerators

Jebkurā gadījumā šī ir mana Disjoint Set PHP 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 saviem lietotājiem ieteikt jaunus draugus, un tad pieņemsim, ka mums ir seši cilvēki, kuriem jau ir izveidotas šādas draugu attiecības:

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

Izmantojot Union-Find algoritmu šīm atsevišķajām grupām, mums vajadzētu atrast sekojošo:

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

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

Protams, šādā nelielā piemērā jūs pats varētu viegli pamanīt šo faktu, taču šī algoritma efektivitāte ļauj to mērogot līdz miljardiem cilvēku un draugu grupām.