Onsamehangende stel (Unie-Vind-algoritme) in PHP

Gepubliseer: 16 Februarie 2025 om 12:30:47 UTC
Laas opgedateer: 26 Januarie 2026 om 10:37:10 UTC

Hierdie artikel bevat 'n PHP-implementering van die Disjoint Set-datastruktuur, algemeen gebruik vir Union-Find in minimum spanningboom-algoritmes.

Hierdie bladsy is masjienvertaal uit Engels om dit vir soveel mense moontlik toeganklik te maak. Ongelukkig is masjienvertaling nog nie 'n volmaakte tegnologie nie, dus kan foute voorkom. As jy verkies, kan jy die oorspronklike Engelse weergawe hier sien:

Disjoint Set (Union-Find Algorithm) in PHP

Die Disjunkte Stel (algemeen gebruik vir Union-Find, ook bekend as Disjunk Stel Unie) is 'n datastruktuur wat gebruik word om 'n verdeling van elemente in disjunkte (nie-oorvleuelende) stelle te bestuur. Dit ondersteun twee sleutelbedrywighede doeltreffend:

Vind: Bepaal tot watter stel 'n element behoort.
Unie: Voeg twee stelle saam.

Hierdie struktuur is veral nuttig in minimum spanningboom-algoritmes, soos Kruskal se algoritme.

Ek het 'n implementering van Kruskal se algoritme wat gebruik word om ewekansige doolhowe te genereer en wat staatmaak op die onderstaande PHP-implementering van Disjoint Set om stelle doeltreffend saam te voeg. As jy belangstel, kan jy dit hier in aksie sien: Kruskal se algoritme doolhof kragopwekker

In elk geval, dit is my PHP-implementering 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]++;
            }
        }
    }
}

Behalwe om doolhowe vir plesier te genereer, kan die Disjoint Set-datastruktuur beslis ook vir werklike scenario's gebruik word.

Stel jou byvoorbeeld 'n sosiale netwerk voor wat nuwe vriende aan sy gebruikers wil voorstel, en kom ons sê dan ons het ses mense met hierdie vriendskapsverhoudings reeds in plek:

1 en 2 is vriende.
2 en 3 is vriende.
4 en 5 is vriende.
6 het geen vriende nie.

As ons die Union-Find-algoritme op hierdie afsonderlike groepe toepas, behoort ons die volgende te vind:

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

Gebaseer hierop sou dit sin maak om voor te stel dat 1 en 3 vriende moet word, want hulle het persoon 2 in gemeen.

Natuurlik, in 'n klein voorbeeld soos hierdie, kan jy hierdie feit maklik self raaksien, maar die doeltreffendheid van hierdie algoritme maak dit moontlik om na miljarde mense en vriendegroepe te skaal.