Disjoint Set (Union-Find Algorithm) ב-PHP

פורסם: 16 בפברואר 2025 בשעה 12:28:58 UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

ה-Disjoint Set (בשימוש נפוץ ל-Union-Find aka Disjoint Set Union) הוא מבנה נתונים המשמש לניהול מחיצה של אלמנטים לקבוצות מנותקות (לא חופפות). הוא תומך בשתי פעולות מפתח ביעילות:

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

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

יש לי יישום של האלגוריתם של 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 אין חברים.

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

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

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

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