מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/הוכחת אלגוריתם 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 == V[1], וMin-Costs[u] מתאר את המחיר הזול ביותר (הידוע) שיעלה לחבר את u לעץ של צומת המוצא s.
כעת בלולאה 10-17 מוצאים כל פעם את הצומת u כך שu אינו בעץ של צומת המוצא s, אך עלות הוספתו היא הנמוכה ביותר. מעדכנים את העלות הכוללת ב13, ומחזירים עלות כוללת זו ב18 עם היציאה מהלולאה.
- אנא הוכח שהאלגוריתם מחזיר את מחירו של עפ"מ בהנתן לו גרף קשיר.
- אנא תאר את השינויים הנדרשים כך שהפונקציה תחזיר את קבוצת קשתות עפ"מ כלשהו (בהנתן גרף קשיר).
|
הנחיות לסעיף הראשון הוכח (באינדוקציה) שכאשר מוצא צומת מ |
