Disjoint Set (Union-Find Algorithm) i PHP

Publicerad: 16 februari 2025 kl. 12:27:23 UTC

Den här artikeln innehåller en PHP-implementering av datastrukturen Disjoint Set, som vanligen används för Union-Find i algoritmer för minimum spaning 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

Disjoint Set (används vanligen för Union-Find aka Disjoint Set Union) är en datastruktur som används för att hantera en partition av element i disjunta (icke-överlappande) uppsättningar. Den stöder två nyckeloperationer effektivt:

Hitta : Bestämmer vilken uppsättning ett element tillhör.
Union : Slår samman två uppsättningar.

Den här strukturen är särskilt användbar i algoritmer med minsta spännträd, såsom Kruskals algoritm.

Jag har en implementering av Kruskals algoritm som används för att generera slumpmässiga labyrinter som förlitar sig på nedanstående PHP-implementering av Disjoint Set för att effektivt slå samman set. Om du är intresserad kan du se den i aktion här: Kruskals algoritm labyrintgenerator

Hur som helst, detta är min PHP-implementering 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 skojs skull kan Disjoint Set-datastrukturen säkert också användas för verkliga scenarier.

Föreställ dig till exempel ett socialt nätverk som skulle vilja föreslå nya vänner till sina användare, och låt oss sedan säga att vi har sex personer med dessa vänrelationer 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.

Utifrån detta skulle det vara vettigt att föreslå att 1 och 3 ska bli vänner, eftersom de har person 2 gemensamt.

Naturligtvis, i ett litet exempel som detta, kan du enkelt upptäcka detta faktum själv, men effektiviteten hos denna algoritm gör att den kan skalas till miljarder människor och vängrupper.