पीएचपीमा असंबद्ध सेट (युनियन-फाइन्ड एल्गोरिदम)
प्रकाशित: २०२५ फेब्रुअरी १६: १२:३३:४४ UTC
यस लेखमा असम्बद्ध सेट डेटा संरचनाको पीएचपी कार्यान्वयन को सुविधा छ, जुन सामान्यतया युनियन-फाइन्डको लागि न्यूनतम विस्तारित ट्री एल्गोरिदममा प्रयोग गरिन्छ।
Disjoint Set (Union-Find Algorithm) in PHP
असम्बद्ध सेट (सामान्यतया युनियन-फाइन्ड उर्फ डिसजोइन्ट सेट युनियनका लागि प्रयोग गरिन्छ) एक डेटा संरचना हो जुन तत्वहरूको विभाजनलाई असम्बद्ध (गैर-अतिव्यापी) सेटहरूमा व्यवस्थापन गर्न प्रयोग गरिन्छ। यसले कुशलतापूर्वक दुई कुञ्जी सञ्चालनहरू समर्थन गर्दछ:
- फेला पार्नुहोस्: तत्व कुन सेटसँग सम्बन्धित छ भनेर निर्धारण गर्दछ ।
- युनियन: दुई सेटहरू एकसाथ मर्ज गर्दछ।
यो संरचना विशेष गरी क्रुस्कलको एल्गोरिदम जस्ता न्यूनतम विस्तारित ट्री एल्गोरिदममा उपयोगी छ।
मसँग क्रुस्कलको एल्गोरिथ्मको कार्यान्वयन छ जुन अनियमित भूलभुलैयाहरू उत्पन्न गर्न प्रयोग गरिन्छ जुन सेटहरू कुशलतापूर्वक मर्ज गर्न असम्बद्ध सेटको तल पीएचपी कार्यान्वयनमा निर्भर गर्दछ। यदि तपाईं इच्छुक हुनुहुन्छ भने, तपाईं यसलाई यहाँ कार्यमा देख्न सक्नुहुन्छ: क्रुस्कलको एल्गोरिदम भूलभुलैया जेनरेटर
जे होस्, यो मेरो पीएचपी कार्यान्वयन हो असम्बद्ध सेट:
{
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 र 3 मित्र बन्नुपर्छ भनेर सुझाव दिनु अर्थपूर्ण हुनेछ, किनकि तिनीहरूसँग व्यक्ति 2 समान छ।
निस्सन्देह, यस प्रकारको सानो उदाहरणमा, तपाईं सजिलैसँग यस तथ्यलाई आफैलाई पत्ता लगाउन सक्नुहुनेछ, तर यस एल्गोरिदमको दक्षताले यसलाई अरबौं मानिसहरू र मित्र समूहहरूमा स्केल गर्न अनुमति दिन्छ।