Disjunkt Set (Union-Find Algorithm) PHP-ben

Megjelent: 2025. február 16. 12:25:29 UTC
Utolsó frissítés: 2026. január 26. 10:36:49 UTC

Ez a cikk bemutatja a Disjoint Set adatszerkezet PHP implementációját, amelyet általánosan használnak az Union-Find minimális spanning fa algoritmusokban.

Ezt az oldalt angolból gépi fordítással készítettük, hogy minél több ember számára elérhető legyen. Sajnos a gépi fordítás még nem tökéletes technológia, ezért előfordulhatnak hibák. Ha szeretné, itt megtekintheti az eredeti angol nyelvű változatot:

Disjoint Set (Union-Find Algorithm) in PHP

A Különálló Halmaz (amelyet általában Union-Find (más néven Disjoint Set Unió) egy adatstruktúra, amelyet az elemek különálló (nem átfedő) halmazokra történő felosztására szolgálnak. Két kulcsfontosságú műveletet hatékonyan támogat:

Find: Meghatározza, melyik halmazhoz tartozik egy elem.
Egyesülés: Két készletet egyesít.

Ez a szerkezet különösen hasznos a minimális spanning tree algoritmusokban, például Kruskal algoritmusában.

Van egy Kruskal algoritmusának implementációja, amelyet véletlenszerű labirintusok generálására használnak, és amely az alábbi PHP Disjoint Set implementációjára támaszkodik a halmazok hatékony összevonásához. Ha érdekel, itt láthatod működés közben: Kruskal algoritmus labirintus generátora

Mindenesetre ez a PHP implementációm a Disjoint Set-hez:

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]++;
            }
        }
    }
}

A labirintusok szórakozásból való generálása mellett a Disjoint Set adatszerkezet valóban használható valós helyzetekben is.

Képzeljük el például egy közösségi hálózatot, amely új barátokat szeretne ajánlani a felhasználóinak, és tegyük fel, hogy hat emberünk van, akik már rendelkeznek ilyen baráti kapcsolatokkal:

Az 1 és a 2 barátok.
2 és 3 barátok.
4 és 5 barátok.
A 6-nak nincsenek barátai.

Az Unió-Kereső algoritmust ezekre a különálló csoportokra alkalmazva a következőket kell találni:

1, 2 és 3 egy csoportban.
4 és 5 egy második csoportban.
Hatos egy harmadik csoportban.

Ennek alapján érdemes azt javasolni, hogy az 1 és a 3 barátok legyenek, mert közös van bennük a 2. személy.

Természetesen egy ilyen kis példában könnyen észreveheted ezt a tényt, de az algoritmus hatékonysága lehetővé teszi, hogy milliárdokra és baráti társaságokra terjedjen.