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

מתוך ויקיפדיה, האנציקלופדיה החופשית
האלגוריתם של פרים
סיבוכיות זמן O(|E| + |V| \log |V|) עריכת הנתון בוויקינתונים
ממציא וויטייך ירניק (1930), רוברט ק. פרים (1957), אדסחר דייקסטרה (1959) עריכת הנתון בוויקינתונים
נקרא על שם רוברט ק. פרים, וויטייך ירניק עריכת הנתון בוויקינתונים
לעריכה בוויקינתונים שמשמש מקור לחלק מהמידע בתבנית
דוגמת הרצה של האלגוריתם של פרים

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

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

בעת מימוש האלגוריתם נעשה שימוש בערימה שמתוכה מוציאים בכל פעם את הצלע המינימלית. אם משתמשים בערימה בינארית סיבוכיות האלגוריתם תהיה (כאשר הוא מספר הקשתות ו- הוא מספר הקודקודים). ניתן לשפרה מעט באמצעות שימוש בערימת פיבונאצ'י ולהגיע ל-.

באופן כללי היעילות של האלגוריתם של פרים טובה מזו של האלגוריתם של קרוסקל. למרות זאת, אם הקלט כבר ממויין לפי משקלי הקשתות או כאשר ניתן למיין אותם בזמן ליניארי, אזי האלגוריתם של קרוסקל יהיה מהיר יותר עם זמן ריצה של .

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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