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

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