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

Udgivet: 16. februar 2025 kl. 12.24.08 UTC

Denne artikel indeholder en PHP-implementering af Disjoint Set-datastrukturen, der almindeligvis bruges til Union-Find i minimumspændingstræ-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

Disjoint Set (almindeligvis brugt til Union-Find alias Disjoint Set Union) er en datastruktur, der bruges til at administrere en opdeling af elementer i usammenhængende (ikke-overlappende) sæt. Det understøtter to nøgleoperationer effektivt:

Find : Bestemmer hvilket sæt et element tilhører.
Union : Fletter to sæt sammen.

Denne struktur er især nyttig i minimumspændende træalgoritmer, såsom Kruskals algoritme.

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

Anyway, dette er min PHP-implementering af 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]++;
            }
        }
    }
}

Udover at generere labyrinter for sjov, kan Disjoint Set-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 har seks personer med disse venneforhold allerede på plads:

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.

Ud fra dette vil det give mening at foreslå, at 1 og 3 skal blive venner, fordi de har person 2 til fælles.

Selvfølgelig kunne du i et lille eksempel som dette nemt selv se dette faktum, men effektiviteten af denne algoritme gør det muligt at skalere til milliarder af mennesker og vennegrupper.