איחוד קבוצות זרות

מימוש בעזרת רשימות מקושרות

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

ניתוח אסימפטוטי

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

מימוש בעזרת יער של קבוצות זרות

יער של קבוצות זרות הוא מימוש של מבנה הנתונים בו כל קבוצה מיוצגת בעזרת עץ.
במימוש הנאיבי, הנציג של כל קבוצה מוגדר להיות שורש העץ. חיפוש עוקב אחרי אבותיהם של איברים בעץ עד למציאת השורש. איחוד ממזג שני עצים בעזרת קביעת שורשו של עץ אחד כאביו של שורשו של העץ השני. במימוש זה, הגישה אינה טובה יותר מגישת הרשימות המקושרות, כיוון שהעצים שנוצרים אינם מאוזנים מבחינת הסתעפות הבנים. בהמשך נציג שני שיפורים אפשריים לשיטת היער.
להלן מימוש אפשרי בשיטה הנאיבית. נשים לב כי לצורך מניעת טיפול במקרי קצה, הגדרנו את אביו של שורש להיות השורש עצמו.
 קטע הקוד הבא הוא פסאודו קוד.
 function MakeSet(x)
     x.parent := x
 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

איחוד על פי דרגה

העקרון המנחה של גישה זו הוא שמירה על עומק עץ מינימלי, בעזרת שרשור העץ הקטן יותר (מבחינת עומק) אל שורשו של העץ הגדול יותר בזמן פעולת איחוד. כתוצאה מכך, העץ המאוחד יהיה בעל עומק גדול יותר אם ורק אם עומקי העצים שאוחדו היו זהים. בהקשר של האלגוריתם, המונח דרגה בא לידי שימוש במקום המונח עומק, מכיוון שכפי שנראה בהמשך, לאחר שיפורים באלגוריתם, ערך זה כבר לא יהיה זהה לעומק העץ על פי הגדרתו.
עצים בעלי איבר יחיד יוגדרו להיות בעלי דרגה 0, ובכל פעם ששני עצים מדרגה  מאוחדים, דרגת העץ המאוחד תוגדר . נשים לב כי עבור עצים מדרגה שונה, דרגת העץ המאוחד תהיה זהה לדרגתו של העץ הגדול מביניהם.
שימוש בטכניקה זו לבדה מניב זמן ריצה של  לכל פעולת איחוד או חיפוש על פני מבנה נתונים בעל  עצמים. פסאודו קוד עבור מימוש הפעולות יצירה ואיחוד תחת טכניקה זו מוצג להלן.
 קטע הקוד הבא הוא פסאודו קוד.
 function MakeSet(x)
     x.parent := x
     x.rank   := 0
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x and y are not already in same set. Merge them.
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

דחיסת מסלולים

השיפור השני שנציג הוא דחיסת מסלולים. נרצה לשטח את מבנה העץ בכל פעם שפעולת חיפוש מבוצעת עליו. הרעיון הבסיסי הוא שכל איבר בו אנו מבקרים בדרך אל השורש, יכול להתחבר ישירות אל השורש (כזכור, כל האיברים בעץ חולקים את אותו השורש שהוא גם הנציג). בפועל, בעת חיפוש, נטפס באופן רקורסיבי במעלה העץ ונערוך את מצביע האב של כל איבר במסלול כך שיצביע אל השורש. העץ המתקבל הוא שטוח יותר, תוצאה אשר ממריצה את זמני הריצה של פעולות עתידיות על מבנה הנתונים. פעולת חיפוש משופרת תמומש כדלהלן.
 קטע הקוד הבא הוא פסאודו קוד.
 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

חסם הדוק יותר

למעשה, שימוש בטכניקות שפורטו לעיל יניב סיבוכיות משוערכת של  בלבד לכל פעולה, כאשר  היא הפונקציה ההופכית לפונקציה , כאשר  היא פונקציית אקרמן, הידועה בתכונתה כפונקציה שגדלה מהר מאוד. בתור ההופכית לפונקציית אקרמן,  היא בפועל פחות מ-5 לכל ערך מעשי של . לדוגמה, המספר , כאשר  הוא אופרטור העצרת, הוא בעל 35,164 ספרות ומתקבל ).
כך, הסיבוכיות המשוערכת לפעולה היא למעשה קבוע זעיר. רוברט טרג'אן היה הראשון להוכיח את החסם על סיבוכיות הזמן במונחים של פונקציית אקרמן בשנת 1975. אמנם הלוגריתם החוזר הוא פונקציה הגדלה מאוד לאט, אך לא לא באותה מידת איטיות כפי של פונקציית אקרמן ההופכית.
פרדמן (Fredman) וסאקס (Saks) הראו בשנת 1989 כי  עצמים בהכרח זוכים לגישה על ידי פעולה כלשהי על מבנה הנתונים בממוצע. תוצאה זו מראה כי החסם שנמצא הוא אופטימלי מבחינה אסימפטוטית.

יישומים

איחוד קבוצות זרות יכול להוות מודל של חלוקה של קבוצה, כדי, לדוגמה, לעקוב אחרי רכיבי קשירות בגרף לא מכוון. מודל זה יכול לעזור לנו בקביעה האם זוג צמתים בגרף שייכים לאותו רכיב קשירות, או האם הוספת קשת בין זוג צמתים תגרום ליצירת מעגל. אלגוריתם איחוד-חיפוש נמצא בשימוש נרחב במערכות בעלות ביצועים ברמה גבוהה המממשות איחוד-גרפים (Unification), תהליך החישוב של הגרף הכללי ביותר המכליל את הגרפים שניתנו כקלט. שימוש נוסף לדוגמה למימוש אלגוריתמים בתורת הגרפים, הוא מימוש האלגוריתם של קרוסקל למציאת עץ פורש מינימלי.
מימוש ביטויי שוויון בשפת Fortran עושה שימוש באלגוריתם איחוד-חיפוש.
יישומים נוספים כוללים שימושים בתחומי עיבוד תמונה, אלגוריתמי היסק וכן במידול מערכות פיזיקליות, כגון חלחול.