Disjoint Set (Union-Find Algorithm) i PHP

Publicerad: 16 februari 2025 kl. 12:27:23 UTC
Senast uppdaterad: 26 januari 2026 kl. 10:36:58 UTC

Denna artikel innehåller en PHP-implementation av Disjunkt Set-datastrukturen, som ofta används för Union-Find i algoritmer med minimum spanning tree.

Denna sida har maskinöversatts från engelska för att göra den tillgänglig för så många som möjligt. Tyvärr är maskinöversättning ännu inte en fulländad teknik, så fel kan uppstå. Om du föredrar det kan du se den engelska originalversionen här:

Disjoint Set (Union-Find Algorithm) in PHP

Den disjunkta mängden (vanligtvis använd för Union-Find, även kallad Disjunkt Mängd-union) är en datastruktur som används för att hantera en uppdelning av element i disjunkta (icke-överlappande) mängder. Den stöder två nyckeloperationer effektivt:

Hitta: Bestämmer vilken mängd ett element tillhör.
Union: Slår ihop två set.

Denna struktur är särskilt användbar i algoritmer med minsta spännande träd, såsom Kruskals algoritm.

Jag har en implementation av Kruskals algoritm som används för att generera slumpmässiga labyrinter och som bygger på den nedanstående PHP-implementeringen av Disjunkt Set för att effektivt slå ihop mängder. Om du är intresserad kan du se den i praktiken här: Kruskals algoritm labyrintgenerator

Hur som helst, detta är min PHP-implementation av 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]++;
            }
        }
    }
}

Förutom att generera labyrinter för nöjes skull kan Disjunkt Set-datastrukturen definitivt också användas för verkliga scenarier.

Föreställ dig till exempel ett socialt nätverk som vill föreslå nya vänner till sina användare, och låt oss sedan säga att vi har sex personer med dessa vänskapsrelationer redan på plats:

1 och 2 är vänner.
2 och 3 är vänner.
4 och 5 är vänner.
6 har inga vänner.

Genom att tillämpa Union-Find-algoritmen på dessa separata grupper bör vi hitta följande:

1, 2 och 3 i en grupp.
4 och 5 i en andra grupp.
6 i en tredje grupp.

Baserat på detta vore det logiskt att föreslå att 1 och 3 borde bli vänner, eftersom de har person 2 gemensamt.

Självklart, i ett litet exempel som detta, skulle du lätt kunna upptäcka detta själv, men algoritmens effektivitet gör att den realistiskt kan skalas till miljarder människor och vänkretsar.