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

Objavljeno: 16. februar 2025. u 12:31:25 UTC

Ovaj članak sadrži PHP implementaciju Disjoint Set strukture podataka, koja se obično koristi za Union-Find u algoritmima minimalnog rasponskog 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 (obično se koristi za Union-Find a.k.a. Disjoint skup Union) je struktura podataka koja se koristi za upravljanje particijom elemenata u disjunktne (ne-preklapajuće) skupove. Efikasno podržava dvije ključne operacije:

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

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

Imam implementaciju Kruskalovog algoritma koji se koristi za generisanje slučajnih labirinta koji se oslanja na donju PHP implementaciju Disjoint Seta za efikasno spajanje skupova. Ako ste zainteresirani, možete ga vidjeti u akciji 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 generiranja labirinta za zabavu, struktura podataka Disjoint Set svakako se može koristiti i za scenarije iz stvarnog života.

Zamislite, na primjer, društvenu mrežu koja bi željela predložiti nove prijatelje svojim korisnicima, a onda recimo da imamo šest ljudi s tim prijateljskim odnosima koji su već uspostavljeni:

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

Primjenjujući Union-Find algoritam 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 zajedničku osobu 2.

Naravno, u malom primjeru kao što je ovaj, lako možete sami uočiti ovu činjenicu, ali učinkovitost ovog algoritma omogućuje mu da se izvedivo skalira na milijarde ljudi i grupa prijatelja.