סיבוכיות זמן ומקום

סיבוכיות זמן:

• מיון E הקשתות הוא O(E log E); כל פעולת איחוד-חיפוש היא כמעט O(1) עם דחיסת מסלולים, ולכן האלגוריתם הקלאסי של Kruskal הוא O(E log E). גרסת בחירת המינימום שנבנה כאן היא O(E²), וזה מתאים לגרפים קטנים.

סיבוכיות מקום:

• O(V) עבור מערך ההורים (בנוסף לקשתות הקלט).

סיכום:

• Kruskal בונה עץ פורש מינימלי (MST) על ידי הוספת הקשת הזולה ביותר שאינה יוצרת מעגל בכל שלב, תוך שימוש באיחוד-חיפוש כדי לבדוק אם נוצרים מעגלים.
• לכל עצי ה-MST אותו משקל כולל, ולכן התשובה יחידה.