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