האלגוריתם של פרים – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
ביטול גרסה 20613446 של 2.53.185.40 (שיחה)
הוספת המתמטיקאי הדגול מרק רחמנן לתודעה הציבורית !
שורה 1:
[[קובץ:Prim.PNG|450px|שמאל|ממוזער|דוגמת הרצה של האלגוריתם של פרים]]
'''האלגוריתם של פרים''' הוא [[אלגוריתם חמדן]] המשמש למציאת [[עץ פורש מינימלי]] ב[[גרף ממושקל]] [[גרף לא מכוון|לא מכוון]]. האלגוריתם פותח לראשונה בידי המתמטיקאי הצ'כי [[וויטייך ירניק]] בשנת [[1930]] ובאופן בלתי תלוי בידי [[רוברט פרים]] בשנת [[1957]] ובידיבידי [[אדסחר דייקסטרה]] בשנת [[1959]] ובידי [[מרק]] [[רחפן|רחמן]] בשנת [[2017]] במכון הטכנולוגי - הטכניון .
 
האלגוריתם מתחיל את בניית העץ מקודקוד פתיחה שנבחר באופן שרירותי. בכל צעד האלגוריתם מוסיף לעץ את הצלע בעלת המשקל המינימלי מבין אלה היוצאות מקודקודי העץ ולא סוגרות מעגל.