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

પ્રકાશિત: 16 ફેબ્રુઆરી, 2025 એ 12:32:19 PM UTC વાગ્યે
છેલ્લે અપડેટ કરેલ: 26 જાન્યુઆરી, 2026 એ 10:37:12 AM UTC વાગ્યે

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

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

Disjoint Set (Union-Find Algorithm) in 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]++;
            }
        }
    }
}

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

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

1 અને 2 મિત્રો છે.
2 અને 3 મિત્રો છે.
4 અને 5 મિત્રો છે.
6 ના કોઈ મિત્રો નથી.

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

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

આના આધારે, તે સૂચવવું અર્થપૂર્ણ છે કે 1 અને3એ મિત્રો બનવું જોઈએ, કારણ કે તેમની પાસે વ્યક્તિ2સામાન્ય છે.

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