מבוא

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

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

הגרף הוא לא מכוון ומשוקלל, ומיוצג באמצעות n (קודקודים 0 עד n - 1) ו-edges, מערך שטוח של שלשות [u0, v0, w0, ...] עבור קשת לא מכוונת u - v במשקל w.

בואו נתחיל!