पीएचपीमध्ये विसंगत संच (युनियन-फाइंड अल्गोरिदम)

प्रकाशित: १६ फेब्रुवारी, २०२५ रोजी १२:२९:१७ PM 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]++;
            }
        }
    }
}

मौजमजेसाठी चक्रव्यूह निर्माण करण्याव्यतिरिक्त, सेट डेटा स्ट्रक्चर चा वापर वास्तविक जीवनातील परिस्थितीसाठी देखील निश्चितपणे केला जाऊ शकतो.

उदाहरणार्थ, एखाद्या सोशल नेटवर्कची कल्पना करा जी आपल्या वापरकर्त्यांना नवीन मित्र सुचवू इच्छिते आणि मग समजा की आपल्याकडे या मित्र संबंधांसह सहा लोक आधीच आहेत:

१ आणि २ मित्र आहेत.
२ आणि ३ मित्र आहेत.
४ आणि ५ मित्र आहेत.
6 ला मित्र नाहीत.

या स्वतंत्र गटांना युनियन-फाइंड अल्गोरिदम लागू केल्यास आपल्याला खालील गोष्टी आढळल्या पाहिजेत:

एका गटात १, २ आणि ३.
दुसऱ्या गटात ४ आणि ५.
तिसऱ्या गटात ६.

याआधारे, 1 आणि 3 ने मित्र बनले पाहिजेत असे सुचविणे योग्य ठरेल, कारण त्यांच्यात व्यक्ती 2 समान आहे.

अर्थात, यासारख्या छोट्या उदाहरणात, आपण स्वत: ही वस्तुस्थिती सहजपणे शोधू शकता, परंतु या अल्गोरिदमची कार्यक्षमता अब्जावधी लोकांना आणि मित्र गटांना सहजपणे स्केल करण्यास अनुमती देते.