מבני נתונים ואלגוריתמים - מחברת קורס/היררכיית האלגוריתמים לבניית עץ פורש

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

בקורס נלמד מספר אלגוריתמים (ודמויי-אלגוריתמים) לבניית עץ פורש. הם מתוארים בתרשים הבא:

היררכיית האלגוריתמים לבניית עץ פורש.
  1. "אלגוריתם" Grow-Tree בונה עץ פורש מגרף לא-מכוון קשיר. קל לשנותו כך שיבנה יער קטן ככל האפשר מגרף לא-מכוון.
  2. אלגוריתם Union-Find מוצא את רכיבי הקשירות של גרף לא מכוון. קל לשנותו כך שיבנה עץ פורש מגרף לא מכוון קשיר.
  3. "אלגוריתם" Grow-MST בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מקרה פרטי של Grow-Tree.
  4. אלגוריתם Kruskal בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST.
  5. אלגוריתם Prim בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST.