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

Հրապարակվել է՝ 16 փետրվարի, 2025 թ., 12:31:15 UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

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

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

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

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

Ամեն դեպքում, սա 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 տվյալների կառուցվածքը, իհարկե, կարող է օգտագործվել նաև իրական կյանքի սցենարների համար:

Պատկերացրեք, օրինակ, սոցիալական ցանց, որը ցանկանում է նոր ընկերներ առաջարկել իր օգտատերերին, և այնուհետև ասենք, որ մենք ունենք վեց հոգի, որոնց ընկերական հարաբերություններն արդեն իսկ գործում են.

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

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

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

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

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