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

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

תבנית:הארה

הבעיה

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

תבנית:מבנה תבנית

אלגוריתם 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

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

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

הנה הסבר לתבנית:קוד בשורה:

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

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

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

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

הסיבוכיות הכוללת, לכן, היא $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 תקף גם כאן: בהנתן גרף לא-מכוון וקשיר, ווריאציית האלגוריתם תבנה עץ פורש. בהרחבה פשוטה של ההוכחה, קל לראות שהאלגוריתם בונה יער במקרה הכללי של גרף לא-מכוון.