Disjointna množica (algoritem Union-Find) v PHP

Objavljeno: 16. februar 2025 ob 12:27:13 pop. UTC
Nazadnje posodobljeno: 26. januar 2026 ob 10:36:58 dop. UTC

Ta članek predstavlja PHP implementacijo podatkovne strukture Disjoint Set, ki se pogosto uporablja za Union-Find v algoritmih minimalnega razpetega drevesa.

Ta stran je bila strojno prevedena iz angleščine, da bi bila dostopna čim večjemu številu ljudi. Žal strojno prevajanje še ni popolna tehnologija, zato lahko pride do napak. Če želite, si lahko izvirno angleško različico ogledate tukaj:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunktna množica (pogosto uporabljena za Union-Find, znano tudi kot Disjoint Set Union) je podatkovna struktura, ki se uporablja za upravljanje razdelitve elementov na disjunktne (neprekrivajoče) množice. Učinkovito podpira dve ključni operaciji:

Najdi: Določa, kateri množici element pripada.
Zveza: Združi dva kompleta.

Ta struktura je še posebej uporabna v algoritmih z minimalnim razpetim drevesom, kot je Kruskalov algoritem.

Imam implementacijo Kruskalovega algoritma, ki se uporablja za generiranje naključnih labirintov in se zanaša na spodnjo PHP implementacijo Disjoint Set za učinkovito združevanje množic. Če vas zanima, si ga lahko ogledate v praksi tukaj: Generator labirinta Kruskalovega algoritma

Kakorkoli, to je moja PHP implementacija 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]++;
            }
        }
    }
}

Poleg ustvarjanja labirintov za zabavo se lahko podatkovna struktura Disjoint Seta zagotovo uporablja tudi v resničnih situacijah.

Predstavljajte si na primer družbeno omrežje, ki bi želelo predlagati nove prijatelje svojim uporabnikom, nato pa recimo, da imamo šest ljudi s temi prijateljskimi odnosi že vzpostavljenimi:

Ena in 2 sta prijatelja.
2 in 3 sta prijatelja.
4 in 5 sta prijatelja.
6 nima prijateljev.

Z uporabo algoritma Union-Find na teh ločenih skupinah bi morali najti naslednje:

1, 2 in 3 v eni skupini.
4 in 5 v drugi skupini.
6 v tretji skupini.

Na podlagi tega bi bilo smiselno predlagati, da bi morala biti 1 in 3 prijatelja, ker imata skupno osebo 2.

Seveda bi lahko v takem majhnem primeru to dejstvo zlahka opazili sami, a učinkovitost tega algoritma mu omogoča, da se lahko razširi na milijarde ljudi in skupin prijateljev.