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

प्रकाशित: २०२५ फेब्रुअरी १६: १२:३३:४४ UTC
पछिल्लो पटक अद्यावधिक गरिएको: २०२६ जनवरी २६: १०:३७:१५ UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

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

फेला पार्नुहोस्: कुन सेटमा तत्व पर्दछ निर्धारण गर्दछ ।
संघ: दुई सेटहरू सँगै मर्ज गर्दछ।

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

मसँग अनियमित भूलभुलैयाहरू उत्पन्न गर्नका लागि प्रयोग गरिएको क्रुस्कलको एल्गोरिदमको कार्यान्वयन छ जुन सेटहरू कुशलतापूर्वक मर्ज गर्न डिज्वाइन्ट सेटको तलको PHP कार्यान्वयनमा निर्भर गर्दछ। यदि तपाईं रुचि राख्नुहुन्छ भने, तपाईं यसलाई यहाँ कार्यमा देख्न सक्नुहुन्छ: क्रुस्कलको एल्गोरिदम भूलभुलैया जेनरेटर

जे भए पनि, यो मेरो PHP कार्यान्वयन हो Disjoint सेट:

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, 2 र 3।
दोस्रो समूहमा ४ र ५ ।
तेस्रो समूहमा ६ ।

यसको आधारमा, यो सुझाव दिनु बुद्धिमानी हुनेछ कि १ र ३ साथी बन्नु पर्छ, किनकि उनीहरूसँग व्यक्ति २ समान छ।

निस्सन्देह, यस प्रकारको सानो उदाहरणमा, तपाईं सजिलैसँग यो तथ्य आफैंमा पत्ता लगाउन सक्नुहुनेछ, तर यस एल्गोरिदमको दक्षताले यसलाई अरबौं व्यक्ति र मित्र समूहहरूमा मापन गर्न अनुमति दिन्छ।