מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/הוכחת אלגוריתם 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'

ההסבר וההוכחה כמעט זהים לאלה שבסעיף הקודם.