Disjunkte Menge (Union-Find-Algorithmus) in PHP

Veröffentlicht: 16. Februar 2025 um 12:24:45 UTC
Zuletzt aktualisiert: 26. Januar 2026 um 10:36:43 UTC

Dieser Artikel stellt eine PHP-Implementierung der Disjunkte Set-Datenstruktur vor, die häufig für Union-Find in Minimal-Spannbaum-Algorithmen 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

Die Disjunkte Menge (üblicherweise für Union-Find, auch Disjunkte Mengenvereinigung genannt) ist eine Datenstruktur, die verwendet wird, um eine Partition von Elementen in disjunkte (nicht überlappende) Mengen zu verwalten. Sie unterstützt zwei Schlüsseloperationen effizient:

Find: Bestimmt, zu welcher Menge ein Element gehört.
Union: Vereint zwei Sets.

Diese Struktur ist besonders nützlich in Minimal-Spannbaum-Algorithmen, wie dem Kruskal-Algorithmus.

Ich habe eine Implementierung von Kruskals Algorithmus, die zur Erzeugung zufälliger Labyrinthe verwendet wird und auf der untenstehenden PHP-Implementierung von Disjoint Set basiert, um Mengen effizient zu verschmelzen. Wenn Sie interessiert sind, können Sie es hier in Aktion sehen: Kruskals Algorithmus-Labyrinth-Generator

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

Neben der Generierung von Labyrinthen zum Spaß kann die Disjunkte-Set-Datenstruktur sicherlich auch für reale Szenarien verwendet werden.

Stellen Sie sich zum Beispiel ein soziales Netzwerk vor, das seinen Nutzern neue Freunde vorschlagen möchte, und nehmen wir an, wir haben sechs Personen mit diesen Freundesbeziehungen:

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

Wenden wir den Union-Find-Algorithmus auf diese separaten Gruppen an, 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 es sinnvoll vorzuschlagen, dass 1 und 3 Freunde werden sollten, weil sie Person 2 gemeinsam haben.

Natürlich könnte man das in einem kleinen Beispiel wie diesem leicht selbst erkennen, aber die Effizienz dieses Algorithmus ermöglicht es realistisch, dass er auf Milliarden von Menschen und Freundesgruppen skalieren kann.