האלגוריתם של פרים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
כפילות |
Ybungalobill (שיחה | תרומות) הרחבה, עריכה |
||
שורה 2:
'''האלגוריתם של פרים''' הוא [[אלגוריתם חמדן]] המשמש למציאת [[עץ פורש מינימלי]] ב[[גרף לא מכוון]].
האלגוריתם מתחיל את
בעת מימוש האלגוריתם
באופן כללי [[יעילות אלגוריתמית|היעילות]] של האלגוריתם של פרים טובה מזו של [[האלגוריתם של קרוסקל]]. למרות זאת, אם הקלט כבר ממויין לפי משקלי הקשתות או כאשר ניתן [[מיון (מדעי המחשב)|למיין]] אותם בזמן ליניארי, אזי האלגוריתם של קרוסקל יהיה מהיר יותר עם זמן ריצה של <math>\ O(E \alpha(E,V))</math>.
▲בעת מימוש האלגוריתם ניתן לעשות שימוש ב[[ערימה]] שמתוכה מוציאים בכל פעם את הצלע המינימלית. ובכך להגיע לסיבוכיות של <math>\ O(|E|log |V|)</math> (כאשר <math>\ E</math> מייצג את מספר הקשתות ו-<math>\ V</math> את מספר הקודקודים). ניתן לשפרה מעט באמצעות שימוש ב[[ערימת פיבונאצ'י]].
== ראו גם ==
| |||