Disjuncte set (Union-Find-algoritme) in PHP

Gepubliceerd: 16 februari 2025 om 12:26:24 UTC
Laatst bijgewerkt: 26 januari 2026 om 10:36:54 UTC

Dit artikel bevat een PHP-implementatie van de Disjoint Set datastructuur, die vaak wordt gebruikt voor Union-Find in minimum spanning tree-algoritmen.

Deze pagina is machinaal uit het Engels vertaald om hem voor zoveel mogelijk mensen toegankelijk te maken. Helaas is machinevertaling nog geen geperfectioneerde technologie, dus er kunnen fouten optreden. Als je dat liever hebt, kun je hier de originele Engelse versie bekijken:

Disjoint Set (Union-Find Algorithm) in PHP

De Disjuncte Verzameling (vaak gebruikt voor Union-Find, ook wel Disjuncte Verzameling Unie genoemd) is een datastructuur die wordt gebruikt om een partitie van elementen in disjuncte (niet-overlappende) verzamelingen te beheren. Het ondersteunt twee belangrijke operaties efficiënt:

Zoeken: Bepaalt tot welke verzameling een element behoort.
Union: Voegt twee sets samen.

Deze structuur is vooral nuttig in algoritmen met minimale spanningsboom, zoals het algoritme van Kruskal.

Ik heb een implementatie van het algoritme van Kruskal die wordt gebruikt voor het genereren van willekeurige doolvelden, die vertrouwt op de onderstaande PHP-implementatie van Disjoint Set om sets efficiënt samen te voegen. Als je geïnteresseerd bent, kun je het hier in actie zien: Kruskal's algoritme-doolhofgenerator

Hoe dan ook, dit is mijn PHP-implementatie van 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]++;
            }
        }
    }
}

Naast het genereren van doolhoven voor de lol, kan de Disjuncte Set-datastructuur zeker ook worden gebruikt voor echte scenario's.

Stel je bijvoorbeeld een sociaal netwerk voor dat nieuwe vrienden aan zijn gebruikers wil voorstellen, en stel dat we zes mensen hebben met deze vriendschapsrelaties die al bestaan:

1 en 2 zijn vrienden.
2 en 3 zijn vrienden.
4 en 5 zijn vrienden.
6 heeft geen vrienden.

Door het Union-Find-algoritme toe te passen op deze afzonderlijke groepen, zouden we het volgende moeten vinden:

1, 2 en 3 in één groep.
4 en 5 in een tweede groep.
6 in een derde groep.

Op basis hiervan zou het logisch zijn om voor te stellen dat 1 en 3 vrienden zouden moeten worden, omdat ze persoon 2 gemeen hebben.

Natuurlijk zou je dit in een klein voorbeeld als dit gemakkelijk zelf kunnen zien, maar de efficiëntie van dit algoritme maakt het haalbaar om te schalen naar miljarden mensen en vriendengroepen.