Onsamehangende stel (Unie-Vind-algoritme) in PHP

Gepubliseer: 16 Februarie 2025 om 12:30:47 UTC

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

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 Disjoint Set (wat algemeen gebruik word vir Union-Find, ook bekend as Disjoint Set Union) is 'n datastruktuur wat gebruik word om 'n verdeling van elemente in onsamehangende (nie-oorvleuelende) stelle te bestuur. Dit ondersteun twee sleutelbedrywighede doeltreffend:

Soek: Bepaal aan watter stel 'n element behoort.
Unie: Voeg twee stelle saam.

Hierdie struktuur is veral nuttig in minimum omvattende boomalgoritmes, soos Kruskal se algoritme.

Ek het 'n implementering van Kruskal se algoritme wat gebruik word vir die generering van ewekansige doolhowe 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 die pret 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 laat ons dan sê dat ons ses mense het met hierdie vriendeverhoudings wat reeds in plek is:

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, moet ons die volgende vind:

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

Op grond hiervan sal dit sinvol wees om voor te stel dat 1 en 3 vriende moet word, want hulle het persoon 2 gemeen.

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