PHP માં ડિસજોઇન્ટ સેટ (યુનિયન-ફાઇન્ડ અલ્ગોરિધમ)

પ્રકાશિત: 16 ફેબ્રુઆરી, 2025 એ 12:32:19 PM UTC વાગ્યે

આ લેખમાં ડિસજોઇન્ટ સેટ ડેટા સ્ટ્રક્ચરનું PHP અમલીકરણ દર્શાવવામાં આવ્યું છે, જે સામાન્ય રીતે ન્યૂનતમ સ્પેનિંગ ટ્રી અલ્ગોરિધમ્સમાં યુનિયન-ફાઇન્ડ માટે વપરાય છે.

આ પૃષ્ઠ શક્ય તેટલા વધુ લોકો સુધી સુલભ બને તે માટે અંગ્રેજીમાંથી મશીન અનુવાદ કરવામાં આવ્યો હતો. કમનસીબે, મશીન અનુવાદ હજુ સુધી સંપૂર્ણ તકનીક નથી, તેથી ભૂલો થઈ શકે છે. જો તમે ઇચ્છો, તો તમે મૂળ અંગ્રેજી સંસ્કરણ અહીં જોઈ શકો છો:

Disjoint Set (Union-Find Algorithm) in PHP

ડિસજોઇન્ટ સેટ (સામાન્ય રીતે યુનિયન-ફાઇન્ડ ઉર્ફે ડિસજોઇન્ટ સેટ યુનિયન માટે વપરાય છે) એ એક ડેટા સ્ટ્રક્ચર છે જેનો ઉપયોગ તત્વોના વિભાજનને ડિસજોઇન્ટ (નોન-ઓવરલેપિંગ) સેટમાં મેનેજ કરવા માટે થાય છે. તે બે મુખ્ય કામગીરીને અસરકારક રીતે સપોર્ટ કરે છે:

શોધો : કયા ઘટકનો સમૂહ છે તે નક્કી કરે છે.
યુનિયન : બે સેટને એકસાથે જોડે છે.

આ માળખું ખાસ કરીને ક્રુસ્કલના અલ્ગોરિધમ જેવા ન્યૂનતમ સ્પેનિંગ ટ્રી અલ્ગોરિધમમાં ઉપયોગી છે.

મારી પાસે ક્રુસ્કલના અલ્ગોરિધમનો અમલ છે જેનો ઉપયોગ રેન્ડમ મેઇઝ જનરેટ કરવા માટે થાય છે જે સેટને અસરકારક રીતે મર્જ કરવા માટે નીચે આપેલા 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]++;
            }
        }
    }
}

મનોરંજન માટે મેઇઝ જનરેટ કરવા ઉપરાંત, ડિસજોઇન્ટ સેટ ડેટા સ્ટ્રક્ચરનો ઉપયોગ વાસ્તવિક જીવનના દૃશ્યો માટે પણ થઈ શકે છે.

ઉદાહરણ તરીકે, એક સોશિયલ નેટવર્કની કલ્પના કરો જે તેના વપરાશકર્તાઓને નવા મિત્રો સૂચવવા માંગે છે, અને પછી ધારો કે આપણી પાસે છ લોકો છે જેમના મિત્ર સંબંધો પહેલાથી જ સ્થાપિત છે:

૧ અને ૨ મિત્રો છે.
૨ અને ૩ મિત્રો છે.
૪ અને ૫ મિત્રો છે.
૬ ને કોઈ મિત્ર નથી.

આ અલગ જૂથો પર યુનિયન-ફાઇન્ડ અલ્ગોરિધમ લાગુ કરવાથી, આપણને નીચે મુજબ મળશે:

એક જૂથમાં ૧, ૨ અને ૩.
બીજા જૂથમાં 4 અને 5.
ત્રીજા જૂથમાં 6.

આના આધારે, એવું સૂચન કરવું યોગ્ય રહેશે કે ૧ અને ૩ એ મિત્ર બનવું જોઈએ, કારણ કે તેમની વચ્ચે બીજી વ્યક્તિ સમાન છે.

અલબત્ત, આવા નાના ઉદાહરણમાં, તમે આ હકીકત સરળતાથી શોધી શકો છો, પરંતુ આ અલ્ગોરિધમની કાર્યક્ષમતા તેને અબજો લોકો અને મિત્ર જૂથો સુધી શક્ય તેટલી ઝડપથી પહોંચાડવાની મંજૂરી આપે છે.