הצגת המקור של הדף "מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Prim"

{{מבני נתונים ואלגוריתמים - מחברת קורס}}



דף זו עוסק באלגוריתם למציאת ה[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/עצים#עץ פורש|עץ הפורש]] הזול ביותר בגרף '''לא מכוון''' בעל טבלת עלויות לקשתות.


{{הארה|1 = 
*אפשר לחשוב על אלגוריתם Prim כ[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra|אלגוריתם Dijkstra]] בשינויים קלים.
*ב[[מבני נתונים ואלגוריתמים - מחברת קורס#ספר הקורס|ספר הקורס]], הפרק "Minimum Spanning Tree" מכסה נושא זה.}} 



{{מבנה תבנית|תמונה=page_white_cplusplus.png|גודל=20px|כותרת=מימוש {{משמאל לימין|C++}}|הסבר=
[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html boost::prim_minimum_spanning_tree]
}} 



==הרעיון הכללי==


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


{{דוגמה|תוכן = 
בתרשים הבא, A מתאר את הגרף בהתחלה. נבחר צומת כלשהו להתחיל בו, נניח צומת <math dir = "ltr">\displaystyle 1</math>.
השלבים הראשונים הם כאלה: 
#העץ מכיל את <math dir = "ltr">\displaystyle \{1\}</math>. השכנים של צמתי העץ הם <math dir = "ltr">\displaystyle 2</math> ו<math dir = "ltr">\displaystyle 6</math>. הזול ביותר להוספה מביניהם הוא 2, ולכן נוסיף אותו.
#העץ מכיל את <math dir = "ltr">\displaystyle \{1, 2\}</math>. השכנים של צמתי העץ הם <math dir = "ltr">\displaystyle 6</math> ו<math dir = "ltr">\displaystyle 3</math>. הזול ביותר להוספה מביניהם הוא 6, ולכן נוסיף אותו.
#העץ מכיל את <math dir = "ltr">\displaystyle \{1, 2, 6\}</math>. השכנים של צמתי העץ הם <math dir = "ltr">\displaystyle 5</math>,<math dir = "ltr">\displaystyle 3</math> ו<math dir = "ltr">\displaystyle 7</math>. הזול ביותר להוספה מביניהם הוא 7, ולכן נוסיף אותו.

[[תמונה:dsa_minimum_spanning_tree_prim_1.png|מרכז|100%|שלבי אלגוריתם Prim ההתחלתיים.]]


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


[[תמונה:dsa_minimum_spanning_tree_prim_2.png|מרכז|100%|שלבי אלגוריתם Prim הסופיים.]]
}}

==פסוודו-קוד==


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



<source lang = "python">
# 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</source>



האתחול דומה מאד לזה שב[[מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra#פסוודו-קוד|אלגוריתם 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#ניתוח סיבוכיות|סיבוכיות אלגוריתם Dijkstra]] ‏-‏ <math dir = "ltr">\displaystyle \Theta((|V| + |E|) \cdot \log(|V|))</math>, וזאת ע"י השוואה פשוטה של שני קטעי הפסוודו-קוד (אין כמעט הבדל ביניהם).


{{מבני נתונים ואלגוריתמים - מחברת קורס|מוגבל}}
[[קטגוריה:מבני נתונים ואלגוריתמים]]