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

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

تتضمن هذه المقالة تنفيذ PHP لهيكل بيانات Disjoint Set، المستخدم عادةً في Union-Find في خوارزميات شجرة الامتداد الدنيا.

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

Disjoint Set (Union-Find Algorithm) in PHP

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

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

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

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

على أية حال، هذا هو تنفيذي لـ 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]++;
            }
        }
    }
}

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

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

1 و 2 صديقان.
2 و 3 صديقان.
4 و 5 صديقان.
6 ليس لديه أصدقاء.

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

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

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

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