Zestaw rozłączny (algorytm Union-Find) w PHP

Opublikowano: 16 lutego 2025 12:26:29 UTC
Ostatnia aktualizacja: 26 stycznia 2026 10:36:54 UTC

W tym artykule przedstawiono implementację struktury danych Disjoint Set, powszechnie stosowaną do Union-Find w algorytmach minimalnych drzew rozpinających.

Ta strona została przetłumaczona maszynowo z języka angielskiego, aby była dostępna dla jak największej liczby osób. Niestety, tłumaczenie maszynowe nie jest jeszcze dopracowaną technologią, więc mogą wystąpić błędy. Jeśli wolisz, możesz wyświetlić oryginalną angielską wersję tutaj:

Disjoint Set (Union-Find Algorithm) in PHP

Zbiór Rozłączny (powszechnie używany w Union-Find, znanym również jako Zjednoczenie Zbiorów Rozłącznych) to struktura danych służąca do zarządzania podziałem elementów na zbiory niespójne (nienakładające się). Efektywnie obsługuje dwie kluczowe operacje:

Znajdź: Określa, do którego zbioru należy dany element.
Union: Łączy dwa zestawy.

Ta struktura jest szczególnie przydatna w algorytmach minimalnych drzew rozpiętych, takich jak algorytm Kruskala.

Mam implementację algorytmu Kruskala używaną do generowania losowych labiryntów, która opiera się na poniższej implementacji PHP Disjoint Set do efektywnego łączenia zbiorów. Jeśli jesteś zainteresowany, możesz zobaczyć to w akcji tutaj: Generator labiryntu algorytmów Kruskala

Tak czy inaczej, oto moja implementacja PHP 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]++;
            }
        }
    }
}

Poza generowaniem labiryntów dla zabawy, struktura danych Disjoint Setu może być również wykorzystywana w rzeczywistych sytuacjach.

Wyobraźmy sobie na przykład sieć społeczną, która chciałaby zasugerować użytkownikom nowych znajomych, a potem załóżmy, że mamy sześć osób z tymi relacjami już istniejącymi:

1 i 2 są przyjaciółmi.
2 i 3 są przyjaciółmi.
4 i 5 to przyjaciele.
Szóstka nie ma przyjaciół.

Stosując algorytm Union-Find do tych oddzielnych grup, powinniśmy znaleźć następujące wynikle:

1, 2 i 3 w jednej grupie.
4 i 5 w drugiej grupie.
6 w trzeciej grupie.

Na tej podstawie miałoby sens zasugerować, że 1 i 3 powinny zostać przyjaciółmi, ponieważ mają wspólną osobę 2.

Oczywiście, w takim małym przykładzie można łatwo zauważyć ten fakt, ale efektywność tego algorytmu pozwala mu skalować się do miliardów osób i grup przyjaciół.