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

'''האלגוריתם של פרים''' הוא [[אלגוריתם]] שמשמש למציאת [[עץ פורש מינימלי]] ב[[גרף לא מכוון]]. הוא נמנה עם ה[[אלגוריתם חמדן|אלגוריתמים החמדניים]].

 

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

 

 

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