PHP တွင် Disjoint Set (Union-Find Algorithm)

ထုတ်ဝေသည်- ၂၀၂၅၊ ဖေဖော်ဝါရီ ၁၆ UTC ၁၂:၃၄:၄၉

ဤဆောင်းပါးတွင် အနိမ့်ဆုံး spanning tree algorithms တွင် Union-Find အတွက် အသုံးများသော Disjoint Set data structure ၏ PHP အကောင်အထည်ဖော်မှုကို ပါရှိသည်။

ဤစာမျက်နှာကို လူများတတ်နိုင်သမျှ ဝင်ရောက်ကြည့်ရှုနိုင်စေရန်အတွက် ဤစာမျက်နှာကို အင်္ဂလိပ်မှ စက်ဖြင့် ဘာသာပြန်ထားခြင်းဖြစ်ပါသည်။ ကံမကောင်းစွာဖြင့်၊ စက်ဘာသာပြန်ခြင်းသည် ပြီးပြည့်စုံသောနည်းပညာမဟုတ်သေးသောကြောင့် အမှားအယွင်းများဖြစ်ပေါ်လာနိုင်သည်။ သင်နှစ်သက်ပါက မူရင်းအင်္ဂလိပ်ဗားရှင်းကို ဤနေရာတွင် ကြည့်ရှုနိုင်ပါသည်။

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (Union-Find (aka Disjoint Set Union) အတွက် အသုံးများသော) သည် ဒြပ်စင်များ၏ အပိုင်းခွဲတစ်ခုအား disjoint (ထပ်နေခြင်းမရှိသော) sets များအဖြစ် စီမံခန့်ခွဲရန် အသုံးပြုသည့် ဒေတာဖွဲ့စည်းပုံဖြစ်သည်။ ၎င်းသည် အဓိက လုပ်ဆောင်ချက်များကို ထိရောက်စွာ ပံ့ပိုးပေးသည်-

ရှာပါ - မည်သည့်အရာနှင့် သက်ဆိုင်သည်ကို သတ်မှတ်ဆုံးဖြတ်သည်။
ပြည်ထောင်စု : နှစ်စုံကို ပေါင်းစည်းပါ။

ဤဖွဲ့စည်းပုံသည် Kruskal's algorithm ကဲ့သို့သော အနည်းဆုံး spanning tree algorithms များတွင် အထူးအသုံးဝင်ပါသည်။

အစုံလိုက်များကို ထိရောက်စွာ ပေါင်းစည်းရန်အတွက် အောက်ဖော်ပြပါ PHP အကောင်အထည်ဖော်မှုအပေါ် အားကိုးသည့် ကျပန်းဝင်္ကပါများကို ဖန်တီးရန်အတွက် အသုံးပြုထားသော Kruskal ၏ အယ်လဂိုရီသမ်ကို အကောင်အထည်ဖော်မှုတစ်ခုရှိသည်။ စိတ်ပါဝင်စားပါက ဤနေရာတွင် လုပ်ဆောင်ရန် Kruskal ၏ Algorithm Maze မီးစက် တွင် ကြည့်ရှုနိုင်ပါသည်။

ဘာပဲဖြစ်ဖြစ်၊ ဒါက 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 algorithm ကို အသုံးပြုခြင်းဖြင့် အောက်ပါတို့ကို ကျွန်ုပ်တို့ ရှာဖွေသင့်သည်-

အုပ်စုတစ်စုတွင် 1၊ 2 နှင့် 3။
ဒုတိယအုပ်စုတွင် ၄ နှင့် ၅။
တတိယအုပ်စုတွင် ၆။

ဤအချက်ကိုအခြေခံ၍ 1 နှင့် 3 သည်တူညီသင့်သည်ဖြစ်သောကြောင့် 1 နှင့် 3 သည်သူငယ်ချင်းဖြစ်သင့်သည်ဟုအကြံပြုခြင်းသည်အဓိပ္ပာယ်ရှိလိမ့်မည်။

ဤကဲ့သို့သော ဥပမာလေးတစ်ခုတွင်၊ ဤအချက်ကို သင်ကိုယ်တိုင် အလွယ်တကူ သိနိုင်သော်လည်း၊ ဤ algorithm ၏ ထိရောက်မှုသည် ၎င်းအား လူပေါင်း ဘီလီယံနှင့်ချီ၍ သူငယ်ချင်းအုပ်စုများသို့ အတိုင်းအတာအထိ ဖြစ်နိုင်ချေရှိစေပါသည်။