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

Objavljeno: 16. veljače 2025. u 12:32:28 UTC

Ovaj članak prikazuje PHP implementaciju strukture podataka Disjoint Set, koja se obično koristi za Union-Find u algoritmima minimalnog razapinjućeg 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

Disjoint Set (obično se koristi za Union-Find aka Disjoint Set Union) je podatkovna struktura 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.
Unija : Spaja dva skupa.

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

Imam implementaciju Kruskalovog algoritma koji se koristi za generiranje nasumičnih labirinta koji se oslanja na donju PHP implementaciju Disjoint Set-a za učinkovito spajanje skupova. Ako ste zainteresirani, možete ga vidjeti na djelu 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 za generiranje 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 želi predložiti nove prijatelje svojim korisnicima, a onda recimo da imamo šest ljudi s ovim prijateljskim odnosima koji su već uspostavljeni:

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

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 skupini.
6 u trećoj skupini.

Na temelju toga, imalo bi smisla predložiti da 1 i 3 postanu prijatelji, jer im je zajednička osoba 2.

Naravno, u malom primjeru kao što je ovaj, mogli biste sami lako uočiti ovu činjenicu, ali učinkovitost ovog algoritma omogućuje mu izvedivo skaliranje na milijarde ljudi i grupa prijatelja.