مجموعة منفصلة (خوارزمية البحث عن الاتحاد) في PHP

نُشرت: ١٦ فبراير ٢٠٢٥ م في ١٢:٢٠:١٧ م UTC
آخر تحديث: ٢٦ يناير ٢٠٢٦ م في ١٠:٣٦:٤١ ص UTC

تتميز هذه المقالة بتنفيذ PHP لبنية بيانات المجموعة المنفصلة، والتي تستخدم عادة في ال Union-Find في خوارزميات شجرة الامتداد الأدنى.

لقد تمت ترجمة هذه الصفحة آليًا من الإنجليزية بهدف جعلها متاحة لأكبر عدد ممكن من الأشخاص. لسوء الحظ، لم يتم تطوير تقنية الترجمة الآلية بعد، لذا قد تحدث أخطاء. إذا كنت تفضل ذلك، يمكنك عرض النسخة الإنجليزية الأصلية هنا:

Disjoint Set (Union-Find Algorithm) in PHP

المجموعة المتباعدة (تستخدم عادة لإيجاد الاتحاد، المعروفة أيضا باسم اتحاد المجموعات المنفصلة) هي بنية بيانات تستخدم لإدارة تقسيم العناصر إلى مجموعات منفصلة (غير متداخلة). يدعم عمليتين رئيسيتين بكفاءة:

البحث: يحدد إلى أي مجموعة ينتمي العنصر.
الاتحاد: يدمج مجموعتين معا.

هذه البنية مفيدة بشكل خاص في خوارزميات شجرة الامتداد الأدنى، مثل خوارزمية كروسكال.

لدي تنفيذ لخوارزمية Kruskal تستخدم لإنشاء متاهات عشوائية تعتمد على تنفيذ PHP أدناه ل Disjoint Set لدمج المجموعات بكفاءة. إذا كنت مهتما، يمكنك مشاهدته أثناء العمل هنا: مولد متاهة خوارزمية كروسكال

على أي حال، هذا هو تنفيذي الخاص ب PHP لمجموعة منفصلة:

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

بعيدا عن إنشاء المتاهات للمتعة، يمكن بالتأكيد استخدام هيكل بيانات المجموعة المتفرقة أيضا في سيناريوهات واقعية.

تخيل، على سبيل المثال، شبكة اجتماعية ترغب في اقتراح أصدقاء جدد لمستخدميها، ثم لنفترض أن لدينا ستة أشخاص لديهم هذه العلاقات الصديقية موجودة بالفعل:

1 و2 أصدقاء.
العمر الثاني والثالث أصدقاء.
4 و5 أصدقاء.
6 ليس لديه أصدقاء.

بتطبيق خوارزمية الاتحاد-البحث على هذه المجموعات المنفصلة، يجب أن نجد التالي:

1، 2 و3 في مجموعة واحدة.
4 و5 في مجموعة ثانية.
6 في المجموعة الثالثة.

استنادا إلى ذلك، من المنطقي اقتراح أن يصبحا 1 و3 صديقين، لأن لديهما شخصا مشتركا في شخصين 2.

بالطبع، في مثال صغير كهذا، يمكنك بسهولة اكتشاف هذه الحقيقة بنفسك، لكن كفاءة هذه الخوارزمية تسمح لها بالتوسع العملي لتشمل مليارات الأشخاص ومجموعات الأصدقاء.