מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Prim
דף זו עוסק באלגוריתם למציאת העץ הפורש הזול ביותר בגרף לא מכוון בעל טבלת עלויות לקשתות.
![]() |
כדאי לדעת: *אפשר לחשוב על אלגוריתם Prim כאלגוריתם Dijkstra בשינויים קלים.
|
![]() |
מימוש C++ |
הרעיון הכללי עריכה
מתחילים מצומת שרירותי כלשהו, ובונים ממנו עץ גדל והולך. בכל שלב מוסיפים לו צומת חדש (שאינו שייך לעץ שלו), שהוא הזול ביותר להוספה.
פסוודו-קוד עריכה
להלן הפסוודו-קוד של אלגוריתם 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
, וMin-Costs[u]
מתאר את המחיר הזול ביותר (הידוע) שיעלה לחבר את u
לעץ של צומת המוצא s
.
כעת בלולאה 10-17 מוצאים כל פעם את הצומת u
כך שu
אינו בעץ של צומת המוצא s
, אך עלות הוספתו היא הנמוכה ביותר. מעדכנים את העלות הכוללת ב13, ומחזירים עלות כוללת זו ב18 עם היציאה מהלולאה.
נכונות וסיבוכיות עריכה
בשיעורי הבית תתבקש להראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow-MST, ומכאן נובעת ההוכחה לנכונותו.
הסיבוכיות היא כסיבוכיות אלגוריתם Dijkstra - , וזאת ע"י השוואה פשוטה של שני קטעי הפסוודו-קוד (אין כמעט הבדל ביניהם).
הפרק הקודם: אלגוריתם Kruskal |
אלגוריתם Prim | הפרק הבא: חיפוש רוחבי |