עץ פורש מינימלי – הבדלי גרסאות

ה[[אלגוריתם]] הראשון למציאת עץ פורש מזערי בגרף לא מכוון הומצא בידי המדען הצ'כי [[אוטקר בוהרובקה]] ב-[[1926]]. מטרתו הייתה מציאת כיסוי חשמלי יעיל של [[מורביה|חבל מורביה]]. כיום משתמשים בשני אלגוריתמים ידועים לגרף לא מכוון: [[האלגוריתם של פרים]] ו[[האלגוריתם של קרוסקל]]. שניהם [[אלגוריתם חמדן|אלגוריתמים חמדניים]]. שניהם רצים בזמן פולינומי, כך שמציאת פתרונות לבעיות כאלו, הם בתחום ה[[סיבוכיות]] של [[P (מדעי המחשב)|P]]. זמן הריצה המדויק שלהם תלוי ב[[מבנה נתונים|מבני הנתונים]] בהם משתמשים (לדוגמה [[ערימת פיבונאצ'י]]).

 

 

האלגוריתם המהיר ביותר עד היום, לעץ פורש מינימלי, פותח על ידי [[ברנרד שאזל]], ומבוסס על האלגוריתם של בוהרובקה. זמן הריצה שלו הוא:

<math>\ O(m \alpha (m,n))</math> כש-<math>\ m</math> מסמן את מספר הקשתות, <math>\ n</math> מסמן את מספר הצמתים ו-<math> \alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}</math> היא [[פונקציית אקרמן|פונקציית אקרמן ההפוכה]].

 

== ראו גם ==