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

דוגמת הרצה של האלגוריתם של פרים

האלגוריתם של פרים הוא אלגוריתם חמדן המשמש למציאת עץ פורש מינימלי בגרף ממושקל לא מכוון. האלגוריתם פותח לראשונה בידי המתמטיקאי הצ'כי וויטייך ירניק בשנת 1930 ובאופן בלתי תלוי בידי רוברט פרים בשנת 1957 ובידי אדסחר דייקסטרה בשנת 1959.

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

בעת מימוש האלגוריתם נעשה שימוש בערימה שמתוכה מוציאים בכל פעם את הצלע המינימלית. אם משתמשים בערימה בינארית סיבוכיות האלגוריתם תהיה $\ O(ElogV+VlogV)$ (כאשר $\ E$ הוא מספר הקשתות ו-$\ V$ הוא מספר הקודקודים). ניתן לשפרה מעט באמצעות שימוש בערימת פיבונאצ'י ולהגיע ל-$\ O(E+V\log V)$.

באופן כללי היעילות של האלגוריתם של פרים טובה מזו של האלגוריתם של קרוסקל. למרות זאת, אם הקלט כבר ממויין לפי משקלי הקשתות או כאשר ניתן למיין אותם בזמן לינארי, אזי האלגוריתם של קרוסקל יהיה מהיר יותר עם זמן ריצה של $\ O(E\ \alpha (E,V))$.

ראו גם

• האלגוריתם של קרוסקל

קישורים חיצוניים

מדיה וקבצים בנושא האלגוריתם של פרים בוויקישיתוף