Disjoint Set (Union-Find Algorithm) v PHP

Publikované: 16. februára 2025 o 12:27:07 UTC
Posledná aktualizácia: 26. januára 2026 o 10:36:57 UTC

Tento článok predstavuje implementáciu PHP dátovej štruktúry Disjoint Set, ktorá sa bežne používa pre Union-Find v algoritmoch minimálneho rozpätého stromu.

Táto stránka bola strojovo preložená z angličtiny, aby bola prístupná čo najväčšiemu počtu ľudí. Žiaľ, strojový preklad ešte nie je dokonalá technológia, takže sa môžu vyskytnúť chyby. Ak chcete, môžete si pozrieť pôvodnú anglickú verziu tu:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunktná množina (bežne používaná pre Union-Find, známa aj ako Disjoint Set Union) je dátová štruktúra používaná na správu rozdelenia prvkov na disjunktné (neprekrývajúce sa) množiny. Efektívne podporuje dve kľúčové operácie:

Nájsť: Určuje, ku ktorej množine prvok patrí.
Zjednotenie: Spája dve sady dokopy.

Táto štruktúra je obzvlášť užitočná v algoritmoch s minimálnym stromovým rozpätím, ako je Kruskalov algoritmus.

Mám implementáciu Kruskalovho algoritmu používanú na generovanie náhodných bludiskov, ktorá sa spolieha na nižšie uvedenú PHP implementáciu Disjoint Set na efektívne zlučovanie množín. Ak máte záujem, môžete to vidieť v akcii tu: Kruskalov generátor bludísk algoritmov

Každopádne, toto je moja PHP implementácia 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]++;
            }
        }
    }
}

Okrem generovania bludiskov pre zábavu sa dátová štruktúra Disjoint Set určite dá použiť aj v reálnych situáciách.

Predstavte si napríklad sociálnu sieť, ktorá by chcela svojim používateľom navrhnúť nových priateľov, a potom povedzme, že máme šesť ľudí, ktorí už majú tieto priateľské vzťahy:

Jednotka a dvojka sú priatelia.
2 a 3 sú priatelia.
4 a 5 sú priatelia.
6 nemá žiadnych priateľov.

Aplikovaním algoritmu Union-Find na tieto samostatné skupiny by sme mali nájsť nasledovné:

1, 2 a 3 v jednej skupine.
4 a 5 v druhej skupine.
6 v tretej skupine.

Na základe toho by dávalo zmysel navrhnúť, že 1 a 3 by sa mali stať priateľmi, pretože majú spoločnú osobu 2.

Samozrejme, v takomto malom príklade by ste si tento fakt ľahko všimli sami, ale efektivita tohto algoritmu mu umožňuje reálne škálovať na miliardy ľudí a skupín priateľov.