מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/מציאת עפ"מ בגרף בעל קשתות בתחום שלם קטן/תשובה

נתבונן בפסוודו-קוד של אלגוריתם Kruskal. נשים לב ש7 ממיינת את הקשתות לפי עלותן. במקרה זה, עפ"י נתוני השאלה, נוכל למיין את הקשתות בזמן לינארי ע"י שימוש במיון ספירה. מעבר לכך לא נשנה כלום.

כעת אם נסתכל באלגוריתם, נוכל לראות בנקל שהסיבוכיות היא רק $\displaystyle \Theta (|V|\cdot \log(|V|)+|E|)$ במקרה הגרוע.