ראשי > עצים פורשים > האלגוריתם של פרים

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

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

האלגוריתם של פרים פועל במידה רבה כמו האלגוריתם של דייקסטרה למציאת המסלולים בקצרים ביותר בגרף. האלגוריתם של פרים הוא בעל התכונה שהקשתות בקבוצת הפתרון המתהווה יהיו תמיד שייכות לעץ יחיד. בניית העץ מתחילה מקודקוד שרירותי והוא הולך וגדל עד שהוא מכסה את כל הגרף. בכל שלב בוחר האלגוריתם את הקשת הקלה ביותר שניתן להוסיף לעץ כדי לחבר אותו עם קודקוד מבודד. כמובן שקשת זו לא תיצור מעגל עם העץ הקיים. כאשר האלגוריתם עוצר הקשתות ב-A יוצרות עץ פורש מינימלי.

גם האלגוריתם של פרים שייך למשפחת ה אלגוריתמים החמדניים משום שבכל שלב הוא בוחר את הקשת בעלת המשקל המינימלי שביכולתו לקחת.

פסאודו קוד

1. TV = { 0 }

2. T = { }

3. while( T has < V-1 edges ) {

4. find (u,v) with least cost, such that
   u is in TV and v isn't in TV

5. if no such edge exists, break

6. add (u,v) to T

7. add v to TV

8. }

הסבר:

הרעיון באלגוריתם של פרים טמון ביכולת להחליט האם ניתן להוסיף קשת חדשה שאינה סוגרת מעגל, אבל קודקוד אחד שלה כבר נמצא בתוך העץ. כדי לממש זאת מחזיק האלגוריתם שני מאגרים: T קבוצת הקשתות המהווה את העץ, והיא גם הפלט. ו-TV זהיא קבוצת הקודקודים הנמצאים בתוך העץ. האלגוריתם מתחיל כאשר שתי הקבוצות ריקות (שורות 1 ו-2). גם כאן תנאי העצירה הוא כאשר T מכיל V-1 קשתות (שורה 4). מאחר ונדאג בכל שלב של שלמות העץ (שורה 4) אנו יכולים להניח שאם ברשותינו V-1 קשתות הרי שיש לנו עץ המחבר V קודקודים.

בכל שלב בלולאה, נבחר מהקת מהגרף המקיימת 2 תנאים: התנאי הראשון הוא שקצה אחד שלה כבר נמצא בתוך העץ והקצה השני אינו בעץ (שורה 4) - כך נבטיח עץ תקין, ללא מעגלים ובעל משקל מינימלי. אם לא קיימת קשת כזאת הרי שהגענו לסוף האלגוריתם (שורה 5). אם מצאנו אחת כזאת כל שנותר לנו הוא להוסיף אותה לעץ ואת הקודקוד השני שלה לרשימת הקודקודים שהעץ מכסה (שורות 6-7).

דוגמת הרצה