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

Opublikowano: 16 lutego 2025 12:26:29 UTC

W tym artykule zaprezentowano implementację struktury danych Disjoint Set w języku PHP, powszechnie stosowanej w algorytmach Union-Find w algorytmach minimalnego drzewa rozpinającego.

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

Disjoint Set (powszechnie używany dla Union-Find, znany również jako Disjoint Set Union) to struktura danych używana do zarządzania partycjonowaniem elementów na rozłączne (nienakładające się) zestawy. Obsługuje ona wydajnie dwie kluczowe operacje:

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

Taka struktura jest szczególnie użyteczna w algorytmach wykorzystujących minimalne drzewo rozpinające, np. algorytm Kruskala.

Mam implementację algorytmu Kruskala używanego do generowania losowych labiryntów, która opiera się na poniższej implementacji PHP Disjoint Set, aby efektywnie scalać zbiory. Jeśli jesteś zainteresowany, możesz zobaczyć to w akcji tutaj: Generator labiryntu algorytmów Kruskala

Tak czy inaczej, oto moja implementacja zestawu rozłącznego w PHP:

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

Oprócz generowania labiryntów dla zabawy, strukturę danych Disjoint Set można również wykorzystać w scenariuszach z życia wziętych.

Wyobraźmy sobie na przykład sieć społecznościową, która chciałaby sugerować swoim użytkownikom nowych znajomych. Załóżmy, że sześć osób ma już nawiązane takie relacje:

1 i 2 są przyjaciółmi.
2 i 3 są przyjaciółmi.
4 i 5 są przyjaciółmi.
6 nie ma przyjaciół.

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

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

Na tej podstawie można by zasugerować, że osoby 1 i 3 powinny się zaprzyjaźnić, ponieważ mają wspólną osobę 2.

Oczywiście w tak małym przykładzie można by to łatwo zauważyć samemu, jednak efektywność tego algorytmu pozwala na jego realne skalowanie do miliardów ludzi i grup znajomych.