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

Objavljeno: 16. februar 2025 ob 12:27:13 pop. UTC

V tem članku je predstavljena PHP implementacija podatkovne strukture Disjoint Set, ki se običajno uporablja za Union-Find v algoritmih minimalnega vpetega 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

Disjoint Set (običajno uporabljen za Union-Find ali Disjoint Set Union) je podatkovna struktura, ki se uporablja za upravljanje razdelitve elementov v ločene (neprekrivajoče se) nize. Učinkovito podpira dve ključni operaciji:

Najdi : Določi, kateri množici pripada element.
Union : združi dva niza skupaj.

Ta struktura je še posebej uporabna pri minimalnih algoritmih vpetega drevesa, kot je Kruskalov algoritem.

Imam implementacijo Kruskalovega algoritma, ki se uporablja za generiranje naključnih labirintov, ki se opira na spodnjo PHP implementacijo Disjoint Set za učinkovito spajanje nizov. Če vas zanima, si ga lahko ogledate v akciji tukaj: Generator labirinta Kruskalovega algoritma

Kakorkoli že, to je moja PHP implementacija Disjuint 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 lahko podatkovno strukturo Disjoint Set zagotovo uporabimo tudi za scenarije iz resničnega življenja.

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

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

Z uporabo algoritma Union-Find za te ločene skupine 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 1 in 3 postaneta prijatelja, saj imata osebo 2 skupno.

Seveda bi lahko v majhnem primeru, kot je ta, to dejstvo zlahka opazili tudi sami, vendar učinkovitost tega algoritma omogoča, da se izvedljivo razširi na milijarde ljudi in skupin prijateljev.