مجموعه مجزا (الگوریتم Union-find) در PHP
منتشر شده: ۱۶ فوریهٔ ۲۰۲۵ ساعت ۱۲:۲۸:۴۵ (UTC)
آخرین به روز رسانی: ۲۶ ژانویهٔ ۲۰۲۶ ساعت ۱۰:۳۷:۰۳ (UTC)
این مقاله پیاده سازی PHP ساختار داده مجموعه های جداگانه را ارائه می دهد که معمولا برای Union-Find در الگوریتم های درخت پوشای حداقل استفاده می شود.
Disjoint Set (Union-Find Algorithm) in PHP
مجموعه گسسته (که معمولا برای Union-Find یا همچنین به نام اتحاد مجموعه های جداگانه استفاده می شود) یک ساختار داده است که برای مدیریت تقسیم بندی عناصر به مجموعه های جدا (غیرهمپوشان) استفاده می شود. این سیستم دو عملیات کلیدی را به طور مؤثر پشتیبانی می کند:
- یافتن: تعیین می کند که یک عنصر به کدام مجموعه تعلق دارد.
- اتحاد: دو مجموعه را با هم ادغام می کند.
این ساختار به ویژه در الگوریتم های درخت پوشای کمینه مانند الگوریتم کروسکال مفید است.
من یک پیاده سازی از الگوریتم Kruskal دارم که برای تولید هزارتوهای تصادفی استفاده می شود و به پیاده سازی PHP زیر از مجموعه های Disjoint برای ادغام بهینه مجموعه ها تکیه دارد. اگر علاقه مند هستید، می توانید آن را در عمل اینجا ببینید: الگوریتم Kruskal مولد پیچ و خم
به هر حال، این پیاده سازی PHP من از Disjoint Set است:
{
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]++;
}
}
}
}
علاوه بر تولید هزارتوها برای سرگرمی، ساختار داده مجموعه های جداگانه قطعا می تواند برای سناریوهای واقعی نیز استفاده شود.
برای مثال، یک شبکه اجتماعی را تصور کنید که می خواهد دوستان جدیدی به کاربرانش پیشنهاد دهد، و فرض کنید شش نفر با این روابط دوستانه از قبل برقرار شده اند:
- ۱ و ۲ دوست هستند.
- ۲ و ۳ دوست هستند.
- ۴ و ۵ دوست هستند.
- ۶ هیچ دوستی ندارد.
با اعمال الگوریتم Union-Find روی این گروه های جداگانه، باید موارد زیر را بیابیم:
- ۱، ۲ و ۳ در یک گروه.
- ۴ و ۵ نفر در گروه دوم.
- ۶ نفر در گروه سوم.
بر اساس این موضوع، منطقی است که پیشنهاد کنیم ۱ و ۳ باید دوست شوند، چون آن ها شخص ۲ مشترک دارند.
البته، در یک مثال کوچک مثل این، خودتان به راحتی می توانید این واقعیت را تشخیص دهید، اما کارایی این الگوریتم به آن اجازه می دهد که به طور عملی به میلیاردها نفر و گروه دوستان گسترش یابد.