מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Union-Find

הגדרה: בהינתן גרף $\displaystyle G=(V,E)$, רכיב הקשירות של $\displaystyle v\in V$ הוא קבוצת כל הצמתים שאפשר להגיע אליהם מ$\displaystyle v$.

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

כדאי לדעת: בספר הקורס, הפרק "Disjoint Sets" (תת-פרק 1) מכסה נושא זה.

מימוש C++ boost::connected_components

הבעיה

נתון גרף לא מכוון $\displaystyle G=(V,E)$. בהינתן שני צמתים כלשהם $\displaystyle u,v\in V$, רוצים לדעת האם $\displaystyle v$ ברכיב הקשירות של $\displaystyle u$ (כלומר, האם יש מסלול ביניהם).

דוגמה: באי באוקיינוס השקט יש שש ערים $\displaystyle 1-6$. בעבר היו כל שתי ערים מחוברות זו לזו בדרך ישירה מאחת לשניה. כעת, בעקבות שיטפון, אלה הדרכים היחידות שנותרו: הקשר בין הערים לאחר השיטפון. נרצה להיות מסוגלים, בהינתן $\displaystyle 2$ ו$\displaystyle 4$ לדוגמה, לענות האם הם עדיין נתן להגיע מהאחד לשני (במקרה זה - לא).

דוגמה: במבני נתונים לקבוצות זרות, ראינו את הבעיה הבאה. סטודנטים מתארגנים לקבוצות לימוד למבחן. נניח את ההנחה המקורבת שאם שני סטודנטים מחליטים ללמוד באותה קבוצה, אז הקבוצה שאליה שייך הסטודנט הראשון מתאחדת עם הקבוצה שאליה שייך הסטודנט השני. נרצה להיות מסוגלים, בהינתן שני סטודנטים, להחליט האם הם שייכים לאותה קבוצה או לא.נניח שיש שמונה סטודנטים: $\displaystyle 1-8$. נתן לחשוב עליהם בתחילה כ-8 קבוצות זרות, שכ"א מורכבת מאיבר יחיד: $\displaystyle 1$ו $\displaystyle 2$מחליטים ללמוד ביחד. $\displaystyle 3$ו $\displaystyle 4$מחליטים ללמוד ביחד. $\displaystyle 5$ו $\displaystyle 6$מחליטים ללמוד ביחד. $\displaystyle 2$ו $\displaystyle 5$מחליטים ללמוד ביחד. $\displaystyle 8$ו $\displaystyle 2$מחליטים ללמוד ביחד. לבסוף, לכן, קבלנו את הקבוצות הזרות $\displaystyle \{1,2,5,6,8\},\{3,4\},\{7\}$: נרצה להיות מסוגלים, בהינתן $\displaystyle 1$ו $\displaystyle 7$ לדוגמה, לענות האם הם שייכים לאותה קבוצה (במקרה זה - לא). כעת כשאנו מכירים גרפים מעט, נוכל לשים לב שאפשר להציג את הבעיה כאחת מתורת הגרפים. כל סטודנט מיוצג ע"י צומת, ואם שני סטודנטים מחליטים ללמוד ביחד, מייצגים זאת ע"י קשת ביניהם. הקשרים בין הסטודנטים. השאלה האם $\displaystyle 1$ו $\displaystyle 7$ לדוגמה, שייכים לאותה קבוצה, שקולה לשאלה האם הם שייכים לאותו רכיב קשירות.

אלגוריתם Union-Find

להלן הפסוודו-קוד לאלגוריתם Union-Find, המשתמש במבנה הנתונים לקבוצות זרות שראינו:

Connected-Components(G)
1	V = V(G)
2	Sets = Make-Array( Length(V) )

3	for v in V
4		Sets[v] = Make-Set()

5	for (u, v) in E(G)
6		if Find-Set(Sets[u]) != Find-Set(Sets[v])
7			Union(Sets[u], Sets[v])

8	return Sets

ולהלן דוגמה לשימוש בו:

1	Sets = Connected-Components(G)

	# Prints True.
1	Print( Find-Set(Sets[1]) == Find-Set([3]) )

	# Prints False.
2	Print( Find-Set(Sets[2]) == Find-Set([3]) )

הנה הסבר לUnion-Find:

• ב2 מייצרים את המערך Sets, המכיל לכל צומת את הקבוצה שלו.
• ב3-4 בונים לכל צומת קבוצה בגודל 1.
• ב5-6 עוברים על כל הקשתות, ומאחדים, לכל קשת, את צומת ההתחלה וצומת הסוף של הקשת אם יש צורך.

ניתוח סיבוכיות

3-4 מייצרות $\displaystyle |V|$ קבוצות זרות שונות, ולאחר מכן מבצעים $\displaystyle \Theta (|E|)$ בדיקות, ולכל היותר $\displaystyle O(V)$ פעולות איחוד. לכן, מבחינת מבנה הנתונים לקבוצות זרות, מדובר בסדרה של $\displaystyle O(|E|)+O(|V|)$ פעולות, מתוכן $\displaystyle O(|V|)$ פעולות מסוג Make-Set. כפי שראינו בניתוח המימוש היעיל למבני נתונים לקבוצות זרות, הסיבוכיות היא $\displaystyle O(|V|\cdot \log(|V|)+|E|+|V|)=O(|V|\cdot \log(|V|)+|E|)$, לכן.

כעת נותר לחשב את עלויות הלולאות עצמן. אם הגרף נתון ברשימת שכנויות, אז 3 אורכת $\displaystyle \Theta (|V|)$, ו5 אורכת $\displaystyle \Theta (|E|)$.

הסיבוכיות הכוללת, לכן, היא $\displaystyle O(|V|\cdot \log(|V|)+|E|)$.

הקשר לאלגוריתם Grow-Tree

אפשר לחשוב על האלגוריתם שראינו זה עתה כמקרה פרטי של "אלגוריתם" Grow-Tree. כדי להדגיש זאת, הנה ווריאציה של האלגוריתם שמחזירה קבוצת קשתות עץ-פורש בהנתן גרף לא-מכוון קשיר.

Connected-Components(G)
1	V = V(G)
2	Sets = Make-Array( Length(V) )

3	E' = Make-List

4	for v in V
5		Sets[v] = Make-Set()

6	for (u, v) in E(G)
7		if Find-Set(Sets[u]) != Find-Set(Sets[v])
8			Union(Sets[u], Sets[v])
9			Insert(E', (u, v))

10	return E'

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

כדאי לדעת: בקורס נלמד מספר אלגוריתמים (ודמויי-אלגוריתמים) לבניית עץ פורש. הם מתוארים בתרשים הבא: היררכיית האלגוריתמים לבניית עץ פורש. "אלגוריתם" Grow-Tree בונה עץ פורש מגרף לא-מכוון קשיר. קל לשנותו כך שיבנה יער קטן ככל האפשר מגרף לא-מכוון. אלגוריתם Union-Find מוצא את רכיבי הקשירות של גרף לא מכוון. קל לשנותו כך שיבנה עץ פורש מגרף לא מכוון קשיר. "אלגוריתם" Grow-MST בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מקרה פרטי של Grow-Tree. אלגוריתם Kruskal בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST. אלגוריתם Prim בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST.

הפרק הקודם: עצים

אלגוריתם Union-Find תרגילים

הפרק הבא: אלגוריתמים למציאת עפ"מ