האלגוריתם של פרים

מבנה נתונים ואלגוריתמים

האלגוריתם של פרים (Prim) דומה מאוד לאלגוריתם של קרוסקל (Kruskal). בעוד שהאלגוריתם של קרוסקל "מגדל" יער של עצים, האלגוריתם של פרים "מגדל" עץ בודד עד שהוא הופך לעץ פורש מינימלית. שני האלגוריתמים משתמשים בגישה החמדנית - הם מוסיפים את הצלע הזולה ביותר שלא סוגרת מעגל. אך במקום לבחור את הצלע הזולה ביותר אשר מקשרת כל זוג עצים יחד, האלגוריתם של פרים מוסיף רק צלעות המצרפות קדקודים לעץ הקיים. (באספקט זה, אלגוריתם פרים דומה מאוד לאלגוריתם של דיאקסטרה למציאת המסלולים הקצרים ביותר).

אלגוריתם פרים עובד ביעילות אם נשמרת רשימה, d[v], של המשקלים הזולים ביותר אשר מקשרים קודקוד v, שאינו עץ, לכל קדקוד שכבר נמצא בעץ. רשימה שניה, pi[v] , שומרת את האינדקס של הקדקודים אשר כבר נמצאים בעץ, ושאליהם קודקוד v יכול להתקשר בעלות של d[v].

הקוד נראה כך:

int *MinimumSpanningTree( Graph g, int n, double **costs ) {

Queue q;

int u, v;

int d[n], *pi;

q = ConsEdgeQueue( g, costs );

pi = ConsPredList( n );

for(i=0;i<n;i++) {

d[i] = INFINITY;

}

/* Choose 0 as the "root" of the MST */

d[0] = 0;

pi[0] = 0;

while ( !Empty( q ) ) {

u = Smallest( g );

for each v in g->adj[u] {

if ( (v in q) && costs[u][v] < d[v] ) {

pi[v] = u;

d[v] = costs[u][v];

}

}

}

return pi;

}

שלבי האלגוריתם הם:

1. בנה את תור הצלעות.

2. בנה רשימה קדומנית של אבות קדומניים של כל צומת.

3. קבע את המרחק "הטוב ביותר" של כל צומת לאינסוף.

4. בחר צומת 0 כ"שורש" העץ הפורש מינימלית (כל צומת יכולה להתאים מאחר שהעץ הפורש כולל בסופו של דבר את כל הצמתים).

5. כל עוד תור הצלעות איננו ריק:

א. הוצא את הצלע הזולה ביותר, u, מהתור.

ב. הרפה את השכנים. אם המרחק של צומת זו מהצומת הקרובה אליה ביותר עד כה גדול מ- d[u][v], עדכן את d[u][v], וקבע את הקדומני של v ל- u.

6. חזור לרשימה הקדומנית.

זמן הסיבוכיות של האלגוריתם הוא O(VlogV + ElogV) = O(ElogV), בדומה לאלגוריתם של קרוסקל. כפי שכבר הוזכר, אלגוריתם פרים יכול להשתפר על ידי שימוש בערמת פיבונאצ'י עד לזמן סיבוכיות של O(E + logV).

המשך ל: ייצוגי גרפים חזור ל: תוכן עניינים