পিএইচপিতে বিচ্ছিন্ন সেট (ইউনিয়ন-ফাইন্ড অ্যালগরিদম)
প্রকাশিত: ১৬ ফেব্রুয়ারী, ২০২৫ এ ১২:২৯:০৮ PM 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 এর মিল রয়েছে।
অবশ্যই, এর মতো একটি ছোট উদাহরণে, আপনি সহজেই এই সত্যটি নিজেই স্পট করতে পারেন, তবে এই অ্যালগরিদমের দক্ষতা এটি কোটি কোটি লোক এবং বন্ধু গোষ্ঠীগুলিতে সম্ভাব্যভাবে স্কেল করতে দেয়।