Disjoint Set (Union-Find Algorithm) në PHP

Publikuar: 16 shkurt 2025 në 12:30:39 e pasdites, UTC
Përditësimi i fundit: 26 janar 2026 në 10:37:09 e paradites, UTC

Ky artikull përmban një implementim PHP të strukturës së të dhënave Disjoint Set, që përdoret zakonisht për Union-Find në algoritmet minimale të pemës.

Kjo faqe u përkthye me makinë nga anglishtja për ta bërë të aksesueshme për sa më shumë njerëz. Fatkeqësisht, përkthimi me makinë nuk është ende një teknologji e përsosur, kështu që mund të ndodhin gabime. Nëse preferoni, mund ta shikoni versionin origjinal në anglisht këtu:

Disjoint Set (Union-Find Algorithm) in PHP

Grupi i shkëputur (përdoret zakonisht për Union-Find i njohur ndryshe si bashkimi i grupeve të shkëputura) është një strukturë e të dhënave që përdoret për të menaxhuar një ndarje të elementeve në grupe të shkëputura (jo të mbivendosura). Ai mbështet dy operacione kryesore në mënyrë efikase:

Gjej: Përcakton se cilit grup i përket një element.
Union: Bashkon dy grupe së bashku.

Kjo strukturë është veçanërisht e dobishme në algoritmet minimale të pemës, siç është algoritmi i Kruskal.

Unë kam një implementim të algoritmit të Kruskal të përdorur për gjenerimin e labirinteve të rastësishme që mbështetet në zbatimin e mëposhtëm PHP të Disjoint Set për të bashkuar në mënyrë efikase grupet. Nëse jeni të interesuar, mund ta shihni në veprim këtu: Gjeneratori i Mazes së Algoritmit të Kruskalit

Gjithsesi, ky është implementimi im PHP i Disjoint Set:

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

Përveç gjenerimit të labirinteve për argëtim, struktura e të dhënave Disjoint Set sigurisht që mund të përdoret edhe për skenarë të jetës reale.

Imagjinoni, për shembull, një rrjet social që do të donte t'u sugjeronte miq të rinj përdoruesve të tij, dhe pastaj le të themi se kemi gjashtë njerëz me këto marrëdhënie miqsh tashmë në vend:

1 dhe 2 janë miq.
2 dhe 3 janë miq.
4 dhe 5 janë miq.
6 nuk ka miq.

Duke aplikuar algoritmin Union-Find në këto grupe të veçanta, duhet të gjejmë sa vijon:

1, 2 dhe 3 në një grup.
4 dhe 5 në një grup të dytë.
6 në një grup të tretë.

Bazuar në këtë, do të kishte kuptim të sugjerohej që 1 dhe 3 duhet të bëhen miq, sepse ata kanë personin 2 të përbashkët.

Sigurisht, në një shembull të vogël si ky, mund ta dalloni lehtësisht vetë këtë fakt, por efikasiteti i këtij algoritmi e lejon atë të shkallëzohet në miliarda njerëz dhe grupe miqsh.