Dizjunktni skup (Algoritam za pronalaženje unije) u PHP-u

Objavljeno: 16. veljače 2025. u 12:32:28 UTC
Zadnje ažuriranje: 26. siječnja 2026. u 10:37:12 UTC

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

Ova je stranica strojno prevedena s engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, strojno prevođenje još nije usavršena tehnologija pa se mogu pojaviti pogreške. Ako želite, izvornu englesku verziju možete pogledati 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. Učinkovito podržava dvije ključne operacije:

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

Ova struktura je osobito korisna u algoritmima minimalnog razapinjućeg stabla, poput Kruskalovog algoritma.

Imam implementaciju Kruskalovog algoritma za generiranje nasumičnih labirinta koja se oslanja na donju PHP implementaciju Disjoint Seta za učinkovito spajanje skupova. Ako vas zanima, možete ga vidjeti u akciji ovdje: Kruskalov algoritam generator labirinta

U svakom slučaju, ovo je moja PHP implementacija Disjoint Seta:

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 stvara labirinte za zabavu, Disjoint Set struktura podataka svakako se može koristiti i za stvarne situacije.

Zamislite, na primjer, društvenu mrežu koja želi predložiti nove prijatelje svojim korisnicima, a zatim recimo da imamo šest ljudi s tim prijateljskim odnosima već uspostavljenim:

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 skupini.

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

Naravno, u malom primjeru poput ovog, lako biste mogli sami uočiti ovu činjenicu, ali učinkovitost ovog algoritma omogućuje mu da se realno proširi na milijarde ljudi i prijateljskih grupa.