Disjoint Set (Union-Find Algorithm) i PHP

Publisert: 16. februar 2025 kl. 12:26:17 UTC

Denne artikkelen inneholder en PHP-implementering av Disjoint Set-datastrukturen, vanligvis brukt for Union-Find i minimum span-tre-algoritmer.

Denne siden er maskinoversatt fra engelsk for å gjøre den tilgjengelig for så mange som mulig. Dessverre er maskinoversettelse ennå ikke en fullkommen teknologi, så det kan forekomme feil. Hvis du foretrekker det, kan du se den engelske originalversjonen her:

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (vanligvis brukt for Union-Find aka Disjoint Set Union) er en datastruktur som brukes til å administrere en partisjon av elementer i usammenhengende (ikke-overlappende) sett. Den støtter to nøkkeloperasjoner effektivt:

Finn : Bestemmer hvilket sett et element tilhører.
Union : Slår sammen to sett.

Denne strukturen er spesielt nyttig i minimum span-tre-algoritmer, for eksempel Kruskals algoritme.

Jeg har en implementering av Kruskals algoritme brukt for å generere tilfeldige labyrinter som er avhengig av PHP-implementeringen nedenfor av Disjoint Set for å effektivt slå sammen sett. Hvis du er interessert, kan du se den i aksjon her: Kruskals algoritme-labyrint-generator

Uansett, dette er 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]++;
            }
        }
    }
}

Bortsett fra å generere labyrinter for moro skyld, kan Disjoint Set-datastrukturen absolutt også brukes til virkelige scenarier.

Tenk deg for eksempel et sosialt nettverk som ønsker å foreslå nye venner til sine brukere, og la oss si at vi har seks personer med disse venneforholdene allerede på plass:

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

Ved å bruke Union-Find-algoritmen på disse separate gruppene, bør vi finne følgende:

1, 2 og 3 i en gruppe.
4 og 5 i en andre gruppe.
6 i en tredje gruppe.

Basert på dette vil det være fornuftig å foreslå at 1 og 3 skal bli venner, fordi de har person 2 til felles.

Selvfølgelig, i et lite eksempel som dette, kan du enkelt oppdage dette faktum selv, men effektiviteten til denne algoritmen gjør at den kan skaleres til milliarder av mennesker og vennegrupper.