Disjunkte Menge (Union-Find-Algorithmus) in PHP

Veröffentlicht: 16. Februar 2025 um 12:24:45 UTC

Dieser Artikel enthält eine PHP-Implementierung der Disjoint Set-Datenstruktur, die häufig für Union-Find in minimalen Spannbaumalgorithmen verwendet wird.

Diese Seite wurde maschinell aus dem Englischen übersetzt, um sie so vielen Menschen wie möglich zugänglich zu machen. Leider ist die maschinelle Übersetzung noch keine ausgereifte Technologie, so dass Fehler auftreten können. Wenn Sie es vorziehen, können Sie sich die englische Originalversion hier ansehen:

Disjoint Set (Union-Find Algorithm) in PHP

Das Disjoint Set (häufig verwendet für Union-Find bzw. Disjoint Set Union) ist eine Datenstruktur, die zur Verwaltung einer Aufteilung von Elementen in disjunkte (nicht überlappende) Mengen verwendet wird. Es unterstützt effizient zwei wichtige Operationen:

Suchen : Bestimmt, zu welcher Menge ein Element gehört.
Union : Fügt zwei Mengen zusammen.

Diese Struktur ist besonders nützlich bei Algorithmen mit minimalem Spannbaum, wie etwa dem Kruskal-Algorithmus.

Ich habe eine Implementierung von Kruskals Algorithmus zur Generierung von Zufallslabyrinthen, die auf der folgenden PHP-Implementierung von Disjoint Set basiert, um Mengen effizient zusammenzuführen. Wenn Sie interessiert sind, können Sie es hier in Aktion sehen: Kruskals Algorithmus-Labyrinth-Generator

Wie dem auch sei, dies ist meine PHP-Implementierung von 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]++;
            }
        }
    }
}

Abgesehen von der spielerischen Generierung von Labyrinthen kann die Disjoint Set-Datenstruktur durchaus auch für reale Szenarien verwendet werden.

Stellen Sie sich beispielsweise ein soziales Netzwerk vor, das seinen Benutzern neue Freunde vorschlagen möchte. Nehmen wir dann an, dass wir sechs Personen haben, mit denen bereits folgende Freundschaftsbeziehungen bestehen:

1 und 2 sind Freunde.
2 und 3 sind Freunde.
4 und 5 sind Freunde.
6 hat keine Freunde.

Wenn wir den Union-Find-Algorithmus auf diese separaten Gruppen anwenden, sollten wir Folgendes finden:

1, 2 und 3 in einer Gruppe.
4 und 5 in einer zweiten Gruppe.
6 in einer dritten Gruppe.

Auf dieser Grundlage wäre der Vorschlag sinnvoll, dass 1 und 3 Freunde werden sollten, da sie Person 2 gemeinsam haben.

Natürlich könnten Sie diese Tatsache in einem kleinen Beispiel wie diesem leicht selbst erkennen, aber die Effizienz dieses Algorithmus ermöglicht eine problemlose Skalierung auf Milliarden von Menschen und Freundeskreisen.