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

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

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

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

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

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

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

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