Disjoint skup (Union-Find algoritam) u PHP-u

Objavljeno: 16. februar 2025. u 12:31:25 UTC
Posljednje ažurirano: 26. januar 2026. u 10:37:11 UTC

Ovaj članak predstavlja PHP implementaciju Disjoint Set strukture podataka, koja se često koristi za Union-Find u algoritmima minimalnog raspona stabla.

Ova stranica je mašinski prevedena sa engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, mašinsko prevođenje još nije usavršena tehnologija, pa može doći do grešaka. Ako želite, možete pogledati originalnu englesku verziju ovdje:

Disjoint Set (Union-Find Algorithm) in PHP

Disjunktni skup (često korišten za Union-Find, poznat i kao Disjoint Set Union) je struktura podataka koja se koristi za upravljanje particijom elemenata u disjunktne (nepreklapajuće) skupove. Efikasno podržava dvije ključne operacije:

Pronađi: Određuje kojem skupu element pripada.
Union: Spaja dva seta.

Ova struktura je posebno korisna u algoritmima minimalnog razapinjućeg stabla, kao što je Kruskalov algoritam.

Imam implementaciju Kruskalovog algoritma koji se koristi za generisanje nasumičnih lavirinta i oslanja se na PHP implementaciju Disjoint Set-a ispod za efikasno spajanje skupova. Ako vas zanima, možete ga vidjeti u praksi ovdje: Kruskalov algoritam Generator labirinta

U svakom slučaju, ovo je moja PHP implementacija Disjoint Set-a:

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]++;
            }
        }
    }
}

Osim što generiše lavirinte za zabavu, Disjoint Set struktura podataka se svakako može koristiti i za stvarne situacije.

Zamislite, na primjer, društvenu mrežu koja želi predložiti nove prijatelje svojim korisnicima, a onda recimo da imamo šest ljudi koji već imaju ove prijateljske odnose:

1 i 2 su prijatelji.
2 i 3 su prijatelji.
4 i 5 su prijatelji.
6 nema prijatelje.

Primjenom algoritma Union-Find na ove odvojene grupe, trebali bismo pronaći sljedeće:

1, 2 i 3 u jednoj grupi.
4 i 5 u drugoj grupi.
6 u trećoj grupi.

Na osnovu toga, imalo bi smisla predložiti da 1 i 3 postanu prijatelji, jer imaju osobu 2 zajedničku.

Naravno, u malom primjeru poput ovog, lako biste mogli sami primijetiti ovu činjenicu, ali efikasnost ovog algoritma omogućava da se realno proširi na milijarde ljudi i grupa prijatelja.