Disjoint Set (Union-Find Algorithm) v PHP

Vydáno: 16. února 2025 v 12:20:20 UTC
Poslední aktualizace: 16. února 2025 v 12:21:08 UTC

Tento článek obsahuje PHP implementaci datové struktury Disjoint Set, běžně používané pro Union-Find v algoritmech minimálního spanning tree.

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

Disjoint Set (běžně používaný pro Union-Find alias Disjoint Set Union) je datová struktura používaná ke správě rozdělení prvků do nesouvislých (nepřekrývajících se) sad. Efektivně podporuje dvě klíčové operace:

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

Tato struktura je zvláště užitečná v algoritmech s minimálním spanning tree, jako je Kruskalův algoritmus.

Mám implementaci Kruskalova algoritmu používaného pro generování náhodných bludišť, který se opírá o níže uvedenou PHP implementaci Disjoint Set pro efektivní sloučení sad. Pokud máte zájem, můžete jej vidět v akci 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ě generování bludišť pro zábavu lze datovou strukturu Disjoint Set jistě použít také pro scénáře ze skutečného života.

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 už máme šest lidí s těmito přátelskými vztahy:

1 a 2 jsou přátelé.
2 a 3 jsou přátelé.
4 a 5 jsou přátelé.
6 nemá žádné přátele.

Aplikováním 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 ve druhé skupině.
6 ve třetí skupině.

Na základě toho by dávalo smysl navrhnout, aby se 1 a 3 stali přáteli, protože mají společnou osobu 2.

Samozřejmě, v malém příkladu, jako je tento, byste si tuto skutečnost mohli snadno všimnout sami, ale účinnost tohoto algoritmu mu umožňuje snadno se škálovat na miliardy lidí a skupin přátel.