Disjoint Set (Union-Find Algorithm) PHP-ում

Հրապարակվել է՝ 16 փետրվարի, 2025 թ., 12:31:15 UTC
Վերջին թարմացումը՝ 26 հունվարի, 2026 թ., 10:37:10 UTC

Այս հոդվածը ներկայացնում է Disjoint Set տվյալների կառուցվածքի PHP իրականացումը, որը սովորաբար օգտագործվում է Union-Find նվազագույն ծավալվող ծառի ալգորիթմներում։

Այս էջը ավտոմատ կերպով թարգմանվել է անգլերենից՝ հնարավորինս շատ մարդկանց համար հասանելի դարձնելու համար: Ցավոք, մեքենայական թարգմանությունը դեռ կատարելագործված տեխնոլոգիա չէ, ուստի կարող են սխալներ առաջանալ: Եթե նախընտրում եք, կարող եք դիտել բնօրինակ անգլերեն տարբերակը այստեղ.

Disjoint Set (Union-Find Algorithm) in PHP

Անջատված հավաքածուն (սովորաբար օգտագործվում է Union-Find aka Disjoint Set Union) տվյալների կառուցվածք է, որն օգտագործվում է տարրերի բաժանումը անջատված (ոչ համընկնող) բազմությունների կառավարելու համար։ Այն արդյունավետորեն աջակցում է երկու հիմնական գործողությունների.

Գտնել: Որոշում է, թե որ բազմությանը է պատկանում տարրը:
Միություն: Միաձուլում է երկու հավաքածու:

Այս կառուցվածքը հատկապես օգտակար է նվազագույն տարածվող ծառի ալգորիթմներում, ինչպիսին է Կրուսկալի ալգորիթմը։

Ես ունեմ Kruskal-ի ալգորիթմի իրականացում, որն օգտագործվում է պատահական լաբիրինթոսներ ստեղծելու համար, որը հիմնված է Disjoint Set-ի ստորեւ բերված PHP իրագործման վրա՝ հավաքածուները արդյունավետ միաձուլելու համար։ Եթե հետաքրքրված եք, կարող եք տեսնել այն գործողության մեջ այստեղ՝ Կրուսկալի ալգորիթմի լաբիրինթոս գեներատոր

Ամեն դեպքում, սա Disjoint Set-ի իմ PHP իրագործումն է.

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

Բացի զվարճանքի համար լաբիրինթոսներ ստեղծելուց, Disjoint Set տվյալների կառուցվածքը, անշուշտ, կարող է օգտագործվել նաեւ իրական կյանքի սցենարների համար։

Պատկերացրեք, օրինակ, սոցիալական ցանցը, որը կցանկանար նոր ընկերներ առաջարկել իր օգտատերերին, ապա ասենք, որ մենք ունենք 6 մարդ, որոնք ունեն այդ ընկերական հարաբերություններն արդեն տեղում.

1-ը եւ 2-ը ընկերներ են։
2-ը եւ 3-ը ընկերներ են։
4-ը եւ 5-ը ընկերներ են։
6-ը ընկերներ չունի։

Կիրառելով Union-Find ալգորիթմը այս առանձին խմբերի վրա՝ մենք պետք է գտնենք հետեւյալը.

1, 2 եւ 3 մեկ խմբում:
4 եւ 5 երկրորդ խմբում:
6 երրորդ խմբում:

Ելնելով դրանից՝ տրամաբանական կլինի առաջարկել, որ 1-ը եւ 3-ը պետք է ընկերներ դառնան, քանի որ նրանք ունեն 2-րդ ընդհանուր անձը։

Իհարկե, այսպիսի փոքրիկ օրինակում դուք հեշտությամբ կարող եք ինքներդ նկատել այս փաստը, բայց այս ալգորիթմի արդյունավետությունը թույլ է տալիս այն հասցնել միլիարդավոր մարդկանց եւ ընկերների խմբերի։