מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Kruskal

דף זו עוסק באלגוריתם למציאת העץ הפורש הזול ביותר בגרף לא מכוון בעל טבלת עלויות לקשתות.

תבנית:הארה

הרעיון הכללי

נפעיל את "אלגוריתם" Grow-Tree, אלא שהסדר שבו נבדוק את הקשתות הוא סדר עולה מבחינת מחירם.

פסוודו-קוד

להלן הפסוודו-קוד של אלגוריתם Kruskal.

מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Kruskal/פסוודו-קוד

1-4 מאתחלות מספר מבני נתונים: תבנית:קוד בשורה מערך הצמתים, $E$ מערך הקשתות, תבנית:קוד בשורה מערך של מבנה הנתונים היעיל לקבוצות זרות, ותבנית:קוד בשורה קבוצת קשתות (במימוש כלשהו, נניח רשימה מקושרת). 5-6 מאתחלות את מבני הנתונים לקבוצות זרות. 7 ממיינת את מערך הקשתות לפי מחיריהן בסדר עולה (באלגוריתם מיון כלשהו, נניח מיון מיזוג). 8-11 דומות ל"אלגוריתם" Grow-Tree, אלא שכעת הקשתות ממויינות לפי מחיריהן, מה שמשפיע על סדר הפעולות. 12 מחזירה את העפ"מ.

נכונות וסיבוכיות

כעת ננתח את הסיבוכיות. 1-6 הן $\mathrm{\Theta }(|V|+|E|)$.‏ אם 7 משתמשת במיון מיזוג, אז היא $O(|E|\cdot \log (|E|))$.‏ 7 ו8-11 הן $O(|V|\cdot \log (|V|)+|E|)$ (לפי ניתוח הסיבוכיות של מימוש רשומות עם איחוד עפ"י גודל). זמן הריצה הכולל, לכן, הוא $O(|V|\cdot \log (|V|)+|E|\cdot \log (|E|))$.