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

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

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

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

באופן כללי [[יעילות אלגוריתמית|היעילות]] של האלגוריתם של פרים טובה מזו של [[האלגוריתם של קרוסקל]]. למרות זאת, אם הקלט כבר ממויין לפי משקלי הקשתות או כאשר ניתן [[מיון (מדעי המחשב)|למיין]] אותם בזמן ליניארי, אזי האלגוריתם של קרוסקל יהיה מהיר יותר עם זמן ריצה של <math>\ O(E\ \alpha(E,V))</math>.

== ראו גם ==
* [[האלגוריתם של קרוסקל]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

[[קטגוריה:אלגוריתמים בתורת הגרפים|פרים]]