Disjoint sæt (Union-Find Algorithm) i PHP

Udgivet: 16. februar 2025 kl. 12.24.08 UTC
Sidst opdateret: 26. januar 2026 kl. 10.36.43 UTC

Denne artikel indeholder en PHP-implementering af Disjunkt Set-datastrukturen, som ofte bruges til Union-Find i minimum spanning tree-algoritmer.

Denne side er blevet maskinoversat fra engelsk for at gøre den tilgængelig for så mange mennesker som muligt. Desværre er maskinoversættelse endnu ikke en perfekt teknologi, så der kan forekomme fejl. Hvis du foretrækker det, kan du se den originale engelske version her:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunkt Set (almindeligvis brugt for Union-Find også kaldet Disjunkt Set Union) er en datastruktur, der bruges til at håndtere en opdeling af elementer i disjunkte (ikke-overlappende) mængder. Den understøtter to nøgleoperationer effektivt:

Find: Bestemmer hvilket sæt et element tilhører.
Union: Sammenlægger to sæt.

Denne struktur er særligt nyttig i minimum spanning tree-algoritmer, såsom Kruskals algoritme.

Jeg har en implementering af Kruskals algoritme, der bruges til at generere tilfældige labyrinter, som er afhængig af nedenstående PHP-implementering af Disjoint Set for effektivt at sammenflette mængder. Hvis du er interesseret, kan du se det i aktion her: Kruskal's Algoritme Maze Generator

Under alle omstændigheder, dette er min PHP-implementering af Disjunkt 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]++;
            }
        }
    }
}

Udover at generere labyrinter for sjov kan Disjunkte Sæt-datastrukturen bestemt også bruges til virkelige scenarier.

Forestil dig for eksempel et socialt netværk, der gerne vil foreslå nye venner til sine brugere, og lad os så sige, at vi allerede har seks personer med disse venneforhold:

1 og 2 er venner.
2 og 3 er venner.
4 og 5 er venner.
6 har ingen venner.

Ved at anvende Union-Find-algoritmen på disse separate grupper, bør vi finde følgende:

1, 2 og 3 i én gruppe.
4 og 5 i en anden gruppe.
6 i en tredje gruppe.

På baggrund af dette ville det give mening at foreslå, at 1 og 3 burde blive venner, fordi de har person 2 til fælles.

Selvfølgelig kunne du i et lille eksempel som dette nemt selv opdage dette, men algoritmens effektivitet gør det muligt at skalere til milliarder af mennesker og vennegrupper.