Disjuncte set (Union-Find-algoritme) in PHP

Gepubliceerd: 16 februari 2025 om 12:26:24 UTC

Dit artikel beschrijft een PHP-implementatie van de Disjoint Set-datastructuur, die veel wordt gebruikt voor Union-Find in algoritmen voor minimale spanning tree.

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 Disjoint Set (vaak gebruikt voor Union-Find, ook bekend als Disjoint Set Union) is een datastructuur die wordt gebruikt om een partitie van elementen in disjoint (niet-overlappende) sets te beheren. Het ondersteunt twee belangrijke bewerkingen efficiënt:

Zoeken : Bepaalt tot welke set een element behoort.
Unie : Voegt twee verzamelingen samen.

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

Ik heb een implementatie van Kruskal's algoritme dat wordt gebruikt voor het genereren van willekeurige doolhoven en dat afhankelijk is van de onderstaande PHP-implementatie van Disjoint Set om sets efficiënt samen te voegen. Als u geïnteresseerd bent, kunt u 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 Disjoint Set-datastructuur zeker ook worden gebruikt voor real-life scenario's.

Stel je bijvoorbeeld een sociaal netwerk voor dat zijn gebruikers nieuwe vrienden wil voorstellen. Stel je dan voor dat we zes mensen hebben die al over deze vriendschapsrelaties beschikken:

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

Als we het Union-Find-algoritme op deze afzonderlijke groepen toepassen, 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 moeten worden, omdat ze persoon 2 gemeen hebben.

Natuurlijk kunt u dit in een klein voorbeeld als dit zelf ook al vaststellen, maar de efficiëntie van dit algoritme zorgt ervoor dat het op een haalbare manier kan worden geschaald naar miljarden mensen en vriendengroepen.