Disjoint Set (Union-Find Algorithm) në PHP

Publikuar: 16 shkurt 2025 në 12:30:39 e pasdites, UTC

Ky artikull përmban një zbatim PHP të strukturës së të dhënave Disjoint Set, zakonisht e përdorur për Union-Find në algoritmet minimale të pemëve që shtrihen.

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

Disjoint Set (zakonisht përdoret për Union-Find a.k.a. Disjoint Set Union) është një strukturë të dhënash që përdoret për të menaxhuar një ndarje të elementeve në grupe destruktive (jo-mbivendosje). Ajo mbështet dy operacione kyçe në mënyrë efikase:

Gjej: Përcakton se cilit element i përket një grupi.
Bashkimi: Shkrin dy grupe së bashku.

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

Kam një zbatim të algoritmit të Kruskal që përdoret për gjenerimin e labirinteve të rastësishme që mbështetet në zbatimin më poshtë PHP të Disjoint Set për të shkrirë në mënyrë efikase setet. Nëse jeni të interesuar, mund ta shihni në veprim këtu: Gjeneratori i Mazes së Algoritmit të Kruskalit

Gjithsesi, ky është zbatimi 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 e jetës reale.

Imagjinoni, për shembull, një rrjet social që do të donte t'u sugjeronte miqve të rinj përdoruesve të tij, dhe pastaj le të themi se kemi gjashtë persona 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ë si më poshtë:

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ë sugjeronim se 1 dhe 3 duhet të bëhen miq, sepse kanë personin 2 të përbashkët.

Natyrisht, në një shembull të vogël si ky, ju mund ta pikasni lehtësisht vetë këtë fakt, por efikasiteti i këtij algoritmi i lejon atij të shkallëzohet në mënyrë të realizueshme në miliarda njerëz dhe grupe miqsh.