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

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

כדאי לדעת: בספר הקורס, הפרק "Minimum Spanning Tree" מכסה נושא זה.

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

הרעיון הכללי

נפעיל את "אלגוריתם" Grow-Tree, אלא שהסדר שבו נבדוק את הקשתות הוא סדר עולה מבחינת מחירם.

דוגמה: בתרשים הבא, A מתאר את הגרף בהתחלה. אם נמיין את הקשתות בסדר עולה, אז $\displaystyle (1,2)$,‏ $\displaystyle (6,7)$, ‏ ו$\displaystyle (5,4)$ יהיו הקשתות הראשונות. B, C, וD מראים את הבחירות בהן. השלבים הראשונים באלגוריתם Kruskal. התרשים הבא ממשיך מהנקודה בה הפסקנו: יש כעת שלושה עצים בעלי שני צמתים כל אחד, ועוד עץ בעל צומת יחיד. נמשיך הלאה, לכן, עד שנקבל עץ יחיד. השלבים הבאים באלגוריתם Kruskal.

פסוודו-קוד

להלן הפסוודו-קוד של אלגוריתם Kruskal.

# Takes a connected undirected graph (G) and a cost table (Edge-Costs)
# Returns a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
MST-Kruskal(G, Edge-Costs)
1	V = V(G)
2	E = E(G)
3	Sets = Make-Array( Length(V) )
4	E' = {}

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

	# Sort the edges by increasing cost, using the
	#	cost-table Edge-Costs.
7	Sort(E) 

8	for (u, v) in E
9		if Find-Set(u) != Find-Set(v)
10			E' = E' ∪ {(u, v)}
11			Union(Sets[u], Sets[v])

12	return E'

1-4 מאתחלות מספר מבני נתונים: V מערך הצמתים, $\displaystyle E$ מערך הקשתות, Sets מערך של מבנה הנתונים היעיל לקבוצות זרות, וE' קבוצת קשתות (במימוש כלשהו, נניח רשימה מקושרת). 5-6 מאתחלות את מבני הנתונים לקבוצות זרות. 7 ממיינת את מערך הקשתות לפי מחיריהן בסדר עולה (באלגוריתם מיון כלשהו, נניח מיון מיזוג). 8-11 דומות ל"אלגוריתם" Grow-Tree, אלא שכעת הקשתות ממויינות לפי מחיריהן, מה שמשפיע על סדר הפעולות. 12 מחזירה את העפ"מ.

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

משפט: אלגוריתם kruskal מחזיר עפ"מ.

הוכחה: כאמור, 7 ממיינת את E לפי מחיר הקשתות. לכן, אם 10 בוחרת בקשת, אז זו הקשת הזולה ביותר מבין הקשתות שעדיין לא השתמשו בהן. הקשתות האחרות ייצרו את העצים שיש עד כה, או שהן חסרות שימוש בשל חיבורן בין צמתים באותו עץ. במילים אחרות, אם 10 בוחרת בקשת, זו בהכרח קשת קלה. מכאן נובע שהאלגוריתם למעשה מממש את "אלגוריתם" Grow-MST.

כעת ננתח את הסיבוכיות. 1-6 הן $\displaystyle \Theta (|V|+|E|)$.‏ אם 7 משתמשת במיון מיזוג, אז היא $\displaystyle O(|E|\cdot \log(|E|))$.‏ 7 ו8-11 הן $\displaystyle O(|V|\cdot \log(|V|)+|E|)$ (לפי ניתוח הסיבוכיות של מימוש רשומות עם איחוד עפ"י גודל). זמן הריצה הכולל, לכן, הוא $\displaystyle O(|V|\cdot \log(|V|)+|E|\cdot \log(|E|))$.