Disjoint Set (Union-Find Algorithm) ב-PHP

פורסם: 16 בפברואר 2025 בשעה 12:28:58 UTC
עודכן לאחרונה: 26 בינואר 2026 בשעה 10:37:05 UTC

מאמר זה מציג מימוש PHP של מבנה הנתונים Disjoint Set, המשמש בדרך כלל ב-Union-Find באלגוריתמים של עץ הכיסוי המינימלי.

עמוד זה תורגם במכונה מאנגלית על מנת להנגיש אותו לכמה שיותר אנשים. למרבה הצער, תרגום מכונה עדיין אינו טכנולוגיה משוכללת, ולכן עלולות להתרחש שגיאות. אם אתה מעדיף, תוכל לצפות בגרסה האנגלית המקורית כאן:

Disjoint Set (Union-Find Algorithm) in PHP

הקבוצה הנפרדת (המשמשת בדרך כלל לאיחוד-איחוד או איחוד קבוצות נפרדות) היא מבנה נתונים המשמש לניהול חלוקה של איברים לקבוצות נפרדות (שאינן חופפות). הוא תומך בשתי פעולות מפתח ביעילות:

מציאה: קובע לאיזו קבוצה שייך אלמנט.
איחוד: מאחד שתי קבוצות יחד.

מבנה זה שימושי במיוחד באלגוריתמים של עץ פריסה מינימלי, כמו האלגוריתם של קרוסקאל.

יש לי מימוש של האלגוריתם של Kruskal המשמש ליצירת מבוכים אקראיים שמסתמך על מימוש 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]++;
            }
        }
    }
}

מלבד יצירת מבוכים בשביל הכיף, מבנה הנתונים Disjoint Set בהחלט יכול לשמש גם לתרחישים אמיתיים.

דמיינו, למשל, רשת חברתית שרוצה להציע חברים חדשים למשתמשים שלה, ואז נניח שיש לנו שישה אנשים עם מערכות יחסים כאלה כבר קיימות:

1 ו-2 הם חברים.
2 ו-3 הם חברים.
4 ו-5 הם חברים.
ל-6 אין חברים.

בהחלת אלגוריתם איחוד-מציאה על קבוצות נפרדות אלו, יש למצוא את הדברים הבאים:

1, 2 ו-3 בקבוצה אחת.
4 ו-5 בקבוצה שנייה.
6 בקבוצה שלישית.

בהתבסס על זה, הגיוני להציע ש-1 ו-3 יהפכו לחברים, כי יש להם את האדם 2 במשותף.

כמובן, בדוגמה קטנה כזו, אפשר היה לזהות זאת בקלות בעצמך, אבל היעילות של האלגוריתם מאפשרת לו להתרחב באופן מעשי למיליארדי אנשים וקבוצות חברים.