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

प्रकाशित: 16 फ़रवरी 2025 को 12:28:03 pm UTC बजे
आखरी अपडेट: 26 जनवरी 2026 को 10:37:01 am 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 समान है।

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