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

האלגוריתם של פרים הוא אלגוריתם חמדן (שבוחר תמיד את ההחלטה הכי טובה עכשיו) למציאת עץ פורש מינימלי. עץ פורש מינימלי הוא אוסף של קשתות שמחבר את כל הקודקודים במשקל הכולל הנמוך ביותר. גרף ממושקל לא מכוון הוא רשת של נקודות וקשתות שבה לכל קשת יש משקל ואין כיוון.
האלגוריתם התחיל מקודקוד שנבחר באופן שרירותי. בכל צעד הוא בוחר את הקשת הקלה ביותר שמחברת את העץ שנבנה לקודקוד חדש, כך שלא יווצר מעגל. הרעיון מבוסס על "תכונת החתך", חוק שמבטיח שהקשת הקלה בחיתוך מסוים אפשרית בעץ מינימלי.
במימוש נהוג להשתמש בערימה (מבנה נתונים שמאפשר להוציא תמיד את הקשת הקלה ביותר). עם ערימה בינארית זמן הריצה הוא O(E log V + V log V). ניתן לשפר זאת בערימת פיבונאצ'י עד O(E + V log V).
במקרים רבים פרים יעיל יותר מאלגוריתם קרוסקל. אבל אם הקשתות ממוינות מראש, קרוסקל יכול להיות מהיר יותר בזמן ריצה מסוים.
האלגוריתם הוצג לראשונה על ידי וויטייך ירניק ובאופן בלתי תלוי על ידי רוברט פרים ואדסחר דייקסטרה.

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