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

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

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