مجموعه مجزا (الگوریتم Union-find) در PHP

منتشر شده: ۱۶ فوریهٔ ۲۰۲۵ ساعت ۱۲:۲۸:۴۵ (UTC)

این مقاله دارای یک پیاده سازی PHP از ساختار داده Disjoint Set است که معمولا برای Union-Find در حداقل الگوریتم های درخت پوشا استفاده می شود.

این صفحه ماشینی از انگلیسی ترجمه شد تا در دسترس هر چه بیشتر مردم باشد. متأسفانه، ترجمه ماشینی هنوز یک فناوری کامل نشده است، بنابراین ممکن است خطاهایی رخ دهد. در صورت تمایل می توانید نسخه اصلی انگلیسی را در اینجا مشاهده کنید:

Disjoint Set (Union-Find Algorithm) in PHP

مجموعه جدا (معمولا برای Union-Find با نام مستعار Disjoint Set Union استفاده می شود) یک ساختار داده است که برای مدیریت پارتیشن بندی عناصر به مجموعه های جدا (غیر همپوشانی) استفاده می شود. از دو عملیات کلیدی به طور موثر پشتیبانی می کند:

یافتن: تعیین می کند که یک عنصر به کدام مجموعه تعلق دارد.
اتحاد: دو مجموعه را با هم ادغام می کند.

این ساختار به ویژه در الگوریتم های درخت پوشا مانند الگوریتم Kruskal مفید است.

من یک پیاده سازی از الگوریتم Kruskal دارم که برای تولید پیچ و خم های تصادفی استفاده می شود که به پیاده سازی PHP زیر از Disjoint Set برای ادغام کارآمد مجموعه ها متکی است. اگر علاقه مند هستید، می توانید آن را در عمل در اینجا مشاهده کنید: الگوریتم Kruskal مولد پیچ و خم

به هر حال، این پیاده سازی PHP من از Disjoint Set است:

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]++;
            }
        }
    }
}

به غیر از تولید پیچ و خم برای سرگرمی، ساختار داده Disjoint Set مطمئنا می تواند برای سناریوهای واقعی نیز استفاده شود.

به عنوان مثال ، یک شبکه اجتماعی را تصور کنید که می خواهد دوستان جدیدی را به کاربران خود پیشنهاد دهد ، و سپس فرض کنید که ما شش نفر با این روابط دوستانه در حال حاضر وجود دارد:

1 و 2 دوست هستند.
2 و 3 دوست هستند.
4 و 5 دوست هستند.
6 هیچ دوستی ندارد.

با استفاده از الگوریتم Union-Find در این گروه های جداگانه، باید موارد زیر را پیدا کنیم:

1، 2 و 3 در یک گروه.
4 و 5 در گروه دوم.
6 نفر در گروه سوم.

بر این اساس، منطقی است که پیشنهاد کنیم 1 و 3 باید با هم دوست شوند، زیرا آنها شخص 2 مشترک دارند.

البته، در یک مثال کوچک مانند این، شما به راحتی می توانید این واقعیت را خودتان تشخیص دهید، اما کارایی این الگوریتم به آن اجازه می دهد تا به میلیاردها نفر و گروه های دوستانه مقیاس شود.