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

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