Disjoint Set (Union-Find Algorithm) v PHP

Vydáno: 16. února 2025 v 12:20:20 UTC
Poslední aktualizace: 26. ledna 2026 v 10:36:42 UTC

Tento článek představuje PHP implementaci datové struktury Disjoint Set, běžně používané pro Union-Find v algoritmech minimálního rozpětí stromu.

Tato stránka byla strojově přeložena z angličtiny, aby byla přístupná co největšímu počtu lidí. Strojový překlad bohužel ještě není dokonalá technologie, takže může dojít k chybám. Pokud si přejete, můžete si prohlédnout původní anglickou verzi zde:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunktní množina (běžně používaná pro Union-Find, také známou jako Disjoint Set Union) je datová struktura používaná ke správě rozdělení prvků do disjunktních (nepřekrývajících se) množin. Podporuje dvě klíčové operace efektivně:

Najít: Určuje, do které množiny prvek patří.
Sjednocení: Spojuje dvě sady dohromady.

Tato struktura je zvláště užitečná v algoritmech pro minimální rozpětí stromu, jako je Kruskalův algoritmus.

Mám implementaci Kruskalova algoritmu používanou pro generování náhodných bludišť, která spoléhá na níže uvedenou PHP implementaci Disjoint Set pro efektivní sloučení množin. Pokud máte zájem, můžete to vidět v praxi zde: Kruskalův Algorithm Maze Generator

Každopádně, toto je moje PHP implementace 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]++;
            }
        }
    }
}

Kromě vytváření bludišť pro zábavu lze datovou strukturu Disjoint Set určitě využít i pro reálné situace.

Představte si například sociální síť, která by chtěla svým uživatelům navrhnout nové přátele, a pak řekněme, že máme šest lidí, kteří už mají tyto přátelské vztahy zavedené:

Jednička a dvojka jsou přátelé.
2 a 3 jsou přátelé.
4 a 5 jsou kamarádi.
Šestka nemá žádné přátele.

Aplikací algoritmu Union-Find na tyto samostatné skupiny bychom měli najít následující:

1, 2 a 3 v jedné skupině.
4 a 5 v druhé skupině.
Šest ve třetí skupině.

Na základě toho by dávalo smysl navrhnout, že by se 1 a 3 měly stát přáteli, protože mají společného osobu 2.

Samozřejmě, v takovém malém příkladu byste si toho mohli snadno všimnout sami, ale efektivita tohoto algoritmu mu umožňuje reálně škálovat na miliardy lidí a přátelských skupin.