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

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

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

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

הרעיון הכללי

מתחילים מצומת שרירותי כלשהו, ובונים ממנו עץ גדל והולך. בכל שלב מוסיפים לו צומת חדש (שאינו שייך לעץ שלו), שהוא הזול ביותר להוספה.

דוגמה: בתרשים הבא, A מתאר את הגרף בהתחלה. נבחר צומת כלשהו להתחיל בו, נניח צומת $\displaystyle 1$. השלבים הראשונים הם כאלה: העץ מכיל את $\displaystyle \{1\}$. השכנים של צמתי העץ הם $\displaystyle 2$ ו$\displaystyle 6$. הזול ביותר להוספה מביניהם הוא 2, ולכן נוסיף אותו. העץ מכיל את $\displaystyle \{1,2\}$. השכנים של צמתי העץ הם $\displaystyle 6$ ו$\displaystyle 3$. הזול ביותר להוספה מביניהם הוא 6, ולכן נוסיף אותו. העץ מכיל את $\displaystyle \{1,2,6\}$. השכנים של צמתי העץ הם $\displaystyle 5$,$\displaystyle 3$ ו$\displaystyle 7$. הזול ביותר להוספה מביניהם הוא 7, ולכן נוסיף אותו. שלבי אלגוריתם Prim ההתחלתיים. התרשים הבא ממשיך מהנקודה בה הפסקנו: יש כעת עץ בעל ארבעה צמתים, , ועוד שלשה עצים בעלי צומת יחד. נמשיך הלאה, לכן, עד שנקבל עץ יחיד. שלבי אלגוריתם Prim הסופיים.

פסוודו-קוד

להלן הפסוודו-קוד של אלגוריתם Prim. (הפסוודו-קוד מחזיר רק את מחיר העץ הפורש המינימום (ולא את קשתותיו). (בשיעורי הבית תתבקש לכתוב גרסה מלאה יותר.)

# Takes a connected undirected graph (G) and a cost table (W)
# Returns the cost of a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
MST-Prim(G, Edge-Costs)
1	pq = Make-Priority-Queue()
	
2	Min-Costs = Make-Array(Length(V(G)))
3	Used = Make-Array(Length(V(G)))
	
4	s = V[1]
	
5	for u in V(G)
6		Min-Costs[u] = u == s? 0 : ∞
7		Used[u] = False
8		Insert(pq, u)
		
9	total-cost = 0	
		
10	while Size(pq) > 0
11		u = Delete(pq)
12		Used[u] = True
	
13		total-cost = total-cost + Min-Costs[u]
	
14		for v in A(G, u)
15			if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
16				Min-Costs[v] = Edge-Costs[ (u, v) ]
17				Decrease-Key(pq, v)
	                	
18	return total-cost

האתחול דומה מאד לזה שבאלגוריתם Dijkstra.‏ 1-8 דוחפות את כל הצמתים לתור קדימויות pq, ומאתחלות את Min-Costs כך שצומת המוצא הוא s. ההבדלים הם במערך Used,‏ ובמשמעות Min-Costs;‏ Used[u] מתאר האם כבר חיברנו את u לעץ של צומת המוצא s, וMin-Costs[u] מתאר את המחיר הזול ביותר (הידוע) שיעלה לחבר את u לעץ של צומת המוצא s.

כעת בלולאה 10-17 מוצאים כל פעם את הצומת u כך שu אינו בעץ של צומת המוצא s, אך עלות הוספתו היא הנמוכה ביותר. מעדכנים את העלות הכוללת ב13, ומחזירים עלות כוללת זו ב18 עם היציאה מהלולאה.

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

בשיעורי הבית תתבקש להראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow-MST, ומכאן נובעת ההוכחה לנכונותו.

הסיבוכיות היא כסיבוכיות אלגוריתם Dijkstra ‏-‏ $\displaystyle \Theta ((|V|+|E|)\cdot \log(|V|))$, וזאת ע"י השוואה פשוטה של שני קטעי הפסוודו-קוד (אין כמעט הבדל ביניהם).

הפרק הקודם: אלגוריתם Kruskal

אלגוריתם Prim

הפרק הבא: חיפוש רוחבי