Disjoint skup (algoritam za pronalaženje unije) u PHP-u

Objavio: 19. mart 2025. 21:36:32 UTC

Ovaj članak sadrži PHP implementaciju Disjoint Set strukture podataka, koja se obično koristi za Union-Find u algoritmima minimalnog raspona stabla.

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

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (uobičajeno korišćen za Union-Find, tj. Disjoint Set Union) je struktura podataka koja se koristi za upravljanje particijom elemenata u disjunktne (nepreklapajuće) skupove. Podržava dve ključne operacije efikasno:

Find: Određuje kojem skupu pripada neki element.
Union: Spaja dva skupa.

Ova struktura je posebno korisna u algoritmima za minimalno obuhvatanje stabla, kao što je Kruskalov algoritam.

Imam implementaciju Kruskalovog algoritma koja se koristi za generisanje nasumičnih labirinta i oslanja se na PHP implementaciju Disjoint Set-a ispod kako bi efikasno spajala skupove. Ako ste zainteresovani, možete videti kako to funkcioniše ovde: Kruskalov algoritam Lavirint Generator

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 labirinte iz zabave, struktura podataka Disjoint Set može se sigurno koristiti i za stvarne scenarije.

Zamislite, na primer, društvenu mrežu koja želi da predloži nove prijatelje svojim korisnicima, i recimo da imamo šest ljudi sa već postojećim prijateljskim vezama:

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

Primena Union-Find algoritma na ove odvojene grupe trebalo bi da pokaže sledeće:

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

Na osnovu ovoga, bilo bi logično predložiti da 1 i 3 postanu prijatelji, jer imaju osobu 2 zajedničku.

Naravno, u malom primeru kao što je ovaj, mogli biste lako da primetite ovaj podatak sami, ali efikasnost ovog algoritma omogućava mu da se ostvarivo skalira na milijarde ljudi i prijateljskih grupa.