מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/הוכחת אלגוריתם Prim/תשובה
מראה
1
[עריכה]ראשית נשנה מעט את אלגוריתם Prim:
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 V' = Make-List()
10 while Size(pq) > 0
11 u = Delete(pq)
12 Used[u] = True
13 Insert(V', u)
14 total-cost = total-cost + Min-Costs[u]
15 for v in A(G, u)
16 if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
17 Min-Costs[v] = Edge-Costs[ (u, v) ]
18 Decrease-Key(pq, v)
השינויים היחידים הם ב9 וב13: אנו מחזיקים רשימה מקושרת V'
המכילה את קבוצת הצמתים שצירפנו לעץ הפורש שאליו שייך s
. בכל שלב נצרף את הצומת מחוץ לV'
שהוא הזול ביותר להוספה (כלומר שהוא מחובר בקשת הזולה ביותר המחברת בין צומת בV'
לצומת מחוץ לV'
).
כשמתבוננים בקוד ומבינים אותו כך, קל לראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow MST. קל להראות זאת פורמלית באינדוקציה - ההוכחה דומה מאד לאלגוריתם Kruskal.
2
[עריכה]שוב נשנה מעט את אלגוריתם Prim:
# Takes a connected undirected graph (G) and a cost table (W)
# Returns 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 Neighbor = Make-Array(Length(V(G)))
4 Used = Make-Array(Length(V(G)))
5 s = V[1]
6 for u in V(G)
7 Min-Costs[u] = u == s? 0 : ∞
8 Neighbor[u] = u == s? 0 : ∞
9 Used[u] = False
10 Insert(pq, u)
11 E' = Make-List()
12 while Size(pq) > 0
13 u = Delete(pq)
14 Used[u] = True
15 if Neighbor[u] != ∞
16 Insert(E', (Neighbor[u], u) )
17 total-cost = total-cost + Min-Costs[u]
18 for v in A(G, u)
19 if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
20 Min-Costs[v] = Edge-Costs[ (u, v) ]
21 Neighbor[v] = u
22 Decrease-Key(pq, v)
23 return E'
ההסבר וההוכחה כמעט זהים לאלה שבסעיף הקודם.