שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2017 - Union-Find

(20 נקודות) אנו מתחזקים גרף (לא מכוון) על קבוצה של $n$ קודקודים, תחת הוספת קשתות(אך קשתות לעולם אינן נמחקות לאחר הוספה). הצע מבנה נתונים התומך בפעולות הבאות: א. $Insert(u,v)$ – הוספת קשת מקודקוד $u$ לקודקוד $v$. ב. $Connect?(u,v)$ – האם קיים מסלול כלשהו בין $u$ ל-$v$ החזר true, אחרת החזר false. ניקוד מלא ינתן לתשובה בה הוספת קשת לוקחת $O(\log n)$, שאילתת $Connect$ לוקחת $O(\log n)$ זמן, וגודל מבנה הנתונים הינו $O(n)$.

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

פתרון: הבעיה של מעקב אחר קשירות בגרף תחת הוספת קשתות ניתנת לפתרון יעיל באמצעות מבנה נתונים מסוג **Union-Find** (איחוד-מציאה), המכונה גם מבנה נתונים לקבוצות זרות (Disjoint Set Union). הרעיון המרכזי הוא לתחזק אוסף של קבוצות זרות, כאשר כל קבוצה מייצגת **רכיב קשירות** בגרף. בתחילה, הגרף מכיל $n$ קודקודים ללא קשתות, ולכן כל קודקוד מהווה רכיב קשירות נפרד. מבנה הנתונים יתחיל עם $n$ קבוצות, כאשר כל קבוצה מכילה קודקוד אחד בלבד. **מימוש מבנה הנתונים:** נשתמש במערך `parent` בגודל $n$, כך ש-`parent[i]` מחזיק את "ההורה" של קודקוד $i$ במבנה העצים שמייצג את הקבוצות. כל רכיב קשירות מיוצג כעץ, ושורש העץ (קודקוד $r$ המקיים `parent[r] == r`) הוא ה**נציג** של רכיב הקשירות כולו. כדי לעמוד בדרישות הסיבוכיות, נשתמש בשתי אופטימיזציות: 1. **איחוד לפי גודל (Union by Size):** נתחזק מערך נוסף, `size`, בגודל $n$. עבור כל שורש $r$, `size[r]` יכיל את מספר הקודקודים בעץ ש-`r` הוא שורשו. כאשר מאחדים שני עצים עם שורשים $r_1$ ו-$r_2$, נחבר את שורש העץ הקטן יותר להיות בן של שורש העץ הגדול יותר. זה מבטיח שגובה העצים יישאר נמוך, בסדר גודל של $O(\log n)$. 2. **כיווץ מסלולים (Path Compression):** במהלך ביצוע פעולת `Find(u)` (המוצאת את נציג הקבוצה של $u$), לאחר מציאת השורש $r$, נגרום לכל הקודקודים שהיו במסלול מ-$u$ ל-$r$ להצביע ישירות על $r$. אופטימיזציה זו "משטיחה" את העצים באופן דרמטי ומאיצה מאוד פעולות עתידיות. **מיפוי הפעולות הנדרשות:** א. **`Insert(u,v)`**: פעולה זו ממופה לפעולת `Union(u,v)` במבנה הנתונים. ראשית, נמצא את הנציגים של $u$ ו-$v$ על ידי קריאה ל-`Find(u)` ו-`Find(v)`. אם הנציגים זהים, הקודקודים כבר נמצאים באותו רכיב קשירות והוספת הקשת לא משנה את הקשירות, ולכן אין צורך לעשות דבר. אם הנציגים שונים, נאחד את שתי הקבוצות (העצים) שלהם באמצעות איחוד לפי גודל. ב. **`Connect?(u,v)`**: פעולה זו בודקת האם קיים מסלול בין $u$ ל-$v$. זה שקול לבדיקה האם $u$ ו-$v$ שייכים לאותו רכיב קשירות. במבנה שלנו, זה מתורגם לבדיקה האם `Find(u) == Find(v)`. אם הנציגים זהים, הפונקציה תחזיר `true`, אחרת `false`. **ניתוח סיבוכיות:** * **סיבוכיות מקום:** אנו משתמשים בשני מערכים (`parent`, `size`) בגודל $n$. לכן, סיבוכיות המקום היא $O(n)$, כנדרש. * **סיבוכיות זמן:** כאשר משתמשים בשתי האופטימיזציות, איחוד לפי גודל וכיווץ מסלולים, הסיבוכיות ה**מופחתת** (amortized) של כל פעולת `Find` או `Union` היא $O(\alpha(n))$, כאשר $\alpha(n)$ היא הפונקציה ההופכית לפונקציית אקרמן. פונקציה זו גדלה לאט באופן קיצוני, ולכל $n$ מעשי ערכה קטן מ-5. סיבוכיות זו טובה משמעותית מהסיבוכיות הנדרשת של $O(\log n)$. * פעולת `Insert(u,v)` מבצעת שתי קריאות `Find` ופעולת איחוד אחת במקרה הגרוע, ולכן זמן הריצה המופחת שלה הוא $O(\alpha(n))$. * פעולת `Connect?(u,v)` מבצעת שתי קריאות `Find`, ולכן זמן הריצה המופחת שלה הוא $O(\alpha(n))$. שתי הפעולות עומדות בדרישת הסיבוכיות של $O(\log n)$. $\blacksquare$