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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי


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


כדאי לדעת:

*אפשר לחשוב על אלגוריתם Prim כאלגוריתם Dijkstra בשינויים קלים.



מימוש C++

boost::prim_minimum_spanning_tree


הרעיון הכללי[עריכה]

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




דוגמה:

בתרשים הבא, A מתאר את הגרף בהתחלה. נבחר צומת כלשהו להתחיל בו, נניח צומת . השלבים הראשונים הם כאלה:

  1. העץ מכיל את . השכנים של צמתי העץ הם ו. הזול ביותר להוספה מביניהם הוא 2, ולכן נוסיף אותו.
  2. העץ מכיל את . השכנים של צמתי העץ הם ו. הזול ביותר להוספה מביניהם הוא 6, ולכן נוסיף אותו.
  3. העץ מכיל את . השכנים של צמתי העץ הם , ו. הזול ביותר להוספה מביניהם הוא 7, ולכן נוסיף אותו.
שלבי אלגוריתם Prim ההתחלתיים.
שלבי אלגוריתם Prim ההתחלתיים.


התרשים הבא ממשיך מהנקודה בה הפסקנו: יש כעת עץ בעל ארבעה צמתים, , ועוד שלשה עצים בעלי צומת יחד. נמשיך הלאה, לכן, עד שנקבל עץ יחיד.


שלבי אלגוריתם 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 ‏-‏ , וזאת ע"י השוואה פשוטה של שני קטעי הפסוודו-קוד (אין כמעט הבדל ביניהם).


הפרק הקודם:
אלגוריתם Kruskal
אלגוריתם Prim הפרק הבא:
חיפוש רוחבי