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

{{#invoke:ParamValidator|validateparams|module_options=יחידה:PV-options}} {{#invoke:תבנית מידע|מידע| | טבלה-עיצוב = width: 22em; font-size: 95%; | כותרת תבנית-עיצוב =background: #B2C6FF; border:1px solid #aaaaaa; border-bottom:0px; | כותרת-עיצוב = background: #B2C6FF; | תמונה = | כיתוב= | תווית-מידע10=מחלקה | תווית-מידע20=סוג | תווית-מידע30=מבנה נתונים | תווית-מידע40=סיבוכיות זמן |סיבוכיות זמן-ויקינתונים=P3752 | תווית-מידע50=סיבוכיות מקום |סיבוכיות מקום-ויקינתונים=P3755 | תווית-מידע60=ממציא |ממציא-ויקינתונים-מרובה=P61 |ממציא-ויקינתונים-פרטים=P577 | תווית-מידע70=נקרא על שם |נקרא על שם-ויקינתונים-מרובה=P138 | תווית-מידע80=הומצא |הומצא-ויקינתונים=P575

}}

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

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

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

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

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

ראו גם

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