PHP में असंयुक्त सेट (यूनियन-फाइंड एल्गोरिथ्म)

प्रकाशित: 16 फ़रवरी 2025 को 12:28:03 pm UTC बजे

यह आलेख डिसजॉइंट सेट डेटा संरचना के PHP कार्यान्वयन को प्रस्तुत करता है, जिसका उपयोग सामान्यतः न्यूनतम स्पैनिंग ट्री एल्गोरिदम में यूनियन-फाइंड के लिए किया जाता है।

इस पृष्ठ को अंग्रेजी से मशीन द्वारा अनुवादित किया गया है ताकि इसे अधिक से अधिक लोगों तक पहुँचाया जा सके। दुर्भाग्य से, मशीन अनुवाद अभी तक एक पूर्ण तकनीक नहीं है, इसलिए त्रुटियाँ हो सकती हैं। यदि आप चाहें, तो आप मूल अंग्रेजी संस्करण यहाँ देख सकते हैं:

Disjoint Set (Union-Find Algorithm) in PHP

डिसजॉइंट सेट (आमतौर पर यूनियन-फाइंड उर्फ डिसजॉइंट सेट यूनियन के लिए इस्तेमाल किया जाता है) एक डेटा संरचना है जिसका उपयोग तत्वों के विभाजन को डिसजॉइंट (गैर-ओवरलैपिंग) सेटों में प्रबंधित करने के लिए किया जाता है। यह दो प्रमुख संचालनों का कुशलतापूर्वक समर्थन करता है:

खोजें : यह निर्धारित करता है कि कोई तत्व किस सेट से संबंधित है।
संघ : दो सेटों को एक साथ मिलाता है।

यह संरचना विशेष रूप से न्यूनतम स्पैनिंग वृक्ष एल्गोरिदम, जैसे क्रुस्कल एल्गोरिदम में उपयोगी है।

मेरे पास क्रस्कल के एल्गोरिथ्म का एक कार्यान्वयन है जिसका उपयोग यादृच्छिक भूलभुलैया बनाने के लिए किया जाता है जो सेटों को कुशलतापूर्वक मर्ज करने के लिए डिसजॉइंट सेट के नीचे दिए गए 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 समान है।

बेशक, इस तरह के एक छोटे से उदाहरण में, आप स्वयं इस तथ्य को आसानी से देख सकते हैं, लेकिन इस एल्गोरिथ्म की दक्षता इसे अरबों लोगों और मित्र समूहों तक व्यावहारिक रूप से लागू करने की अनुमति देती है।