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

प्रकाशित: १६ फेब्रुवारी, २०२५ रोजी १२:२९:१७ PM UTC
शेवटचे अपडेट केलेले: २६ जानेवारी, २०२६ रोजी १०:३७:०६ AM UTC

या लेखात डिसजॉइंट सेट डेटा स्ट्रक्चरची पीएचपी अंमलबजावणी आहे, जी सामान्यत: कमीतकमी स्पॅनिंग ट्री अल्गोरिदममध्ये युनियन-फाइंडसाठी वापरली जाते.

हे पान जास्तीत जास्त लोकांना उपलब्ध व्हावे म्हणून इंग्रजीतून मशीन भाषांतरित करण्यात आले आहे. दुर्दैवाने, मशीन भाषांतर अद्याप परिपूर्ण तंत्रज्ञान नाही, त्यामुळे चुका होऊ शकतात. तुम्हाला हवे असल्यास, तुम्ही मूळ इंग्रजी आवृत्ती येथे पाहू शकता:

Disjoint Set (Union-Find Algorithm) in PHP

डिसजॉइंट सेट (सामान्यत: युनियन-फाइंड उर्फ डिजॉइंट सेट युनियनसाठी वापरला जातो) ही एक डेटा रचना आहे जी घटकांचे विभाजन डिसजॉइंट (नॉन-ओव्हरलॅपिंग) सेटमध्ये व्यवस्थापित करण्यासाठी वापरली जाते. हे दोन प्रमुख ऑपरेशन्सला कार्यक्षमतेने समर्थन देते:

शोधा: घटक कोणत्या संचाचा आहे हे निर्धारित करते.
युनियन: दोन संच एकत्र विलीन करतात.

ही रचना क्रुस्कलच्या अल्गोरिदमसारख्या किमान स्पॅनिंग ट्री अल्गोरिदममध्ये विशेषतः उपयुक्त आहे.

माझ्याकडे यादृच्छिक भूलभुलैया तयार करण्यासाठी वापरल्या जाणार् या क्रुस्कलच्या अल्गोरिदमची अंमलबजावणी आहे जी कार्यक्षमतेने संच विलीन करण्यासाठी डिसजॉइंट सेटच्या खालील 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 ला मित्र नाहीत.

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

एका गटात 1, 2 आणि 3.
दुसर् या गटात4आणि5आहेत.
तिसर् या गटात 6.

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

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