מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם 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 דוחפות את כל הצמתים לתור קדימויות תבנית:קוד בשורה, ומאתחלות את תבנית:קוד בשורה כך שצומת המוצא הוא תבנית:קוד בשורה. ההבדלים הם במערך תבנית:קוד בשורה, ובמשמעות תבנית:קוד בשורה; תבנית:קוד בשורה מתאר האם כבר חיברנו את תבנית:קוד בשורה לעץ של צומת המוצא תבנית:קוד בשורה, ותבנית:קוד בשורה מתאר את המחיר הזול ביותר (הידוע) שיעלה לחבר את תבנית:קוד בשורה לעץ של צומת המוצא תבנית:קוד בשורה.
כעת בלולאה 10-17 מוצאים כל פעם את הצומת תבנית:קוד בשורה כך שתבנית:קוד בשורה אינו בעץ של צומת המוצא תבנית:קוד בשורה, אך עלות הוספתו היא הנמוכה ביותר. מעדכנים את העלות הכוללת ב13, ומחזירים עלות כוללת זו ב18 עם היציאה מהלולאה.
נכונות וסיבוכיות
בשיעורי הבית תתבקש להראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow-MST, ומכאן נובעת ההוכחה לנכונותו.
הסיבוכיות היא כסיבוכיות אלגוריתם Dijkstra - , וזאת ע"י השוואה פשוטה של שני קטעי הפסוודו-קוד (אין כמעט הבדל ביניהם).