Disjoint Set (Union-Find Algorithm) v PHP

Publikované: 16. februára 2025 o 12:27:07 UTC

Tento článok obsahuje PHP implementáciu dátovej štruktúry Disjoint Set, ktorá sa bežne používa pre Union-Find v algoritmoch s minimálnym spanning tree.

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

Disjoint Set (bežne používaný pre Union-Find alias Disjoint Set Union) je dátová štruktúra používaná na riadenie rozdelenia prvkov do nesúvislých (neprekrývajúcich sa) množín. Efektívne podporuje dve kľúčové operácie:

Nájsť : Určuje, do ktorej množiny prvok patrí.
Union : Zlúči dve sady dohromady.

Táto štruktúra je užitočná najmä v algoritmoch s minimálnym spanning tree, ako je Kruskalov algoritmus.

Mám implementáciu Kruskalovho algoritmu, ktorý sa používa na generovanie náhodných bludísk, ktorý sa spolieha na nižšie uvedenú implementáciu PHP Disjoint Set na efektívne zlúčenie množín. Ak máte záujem, môžete si ho pozrieť 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 bludísk pre zábavu sa dátová štruktúra Disjoint Set určite dá použiť aj na scenáre zo skutočného života.

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

1 a 2 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ť toto:

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úť, aby sa 1 a 3 stali priateľmi, pretože majú spoločnú osobu 2.

Samozrejme, v malom príklade, ako je tento, by ste si túto skutočnosť mohli ľahko všimnúť sami, ale efektívnosť tohto algoritmu mu umožňuje reálne sa rozšíriť na miliardy ľudí a skupiny priateľov.