האלגוריתם של קרוסקל

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

האלגוריתם ממיין את הקשתות לפי משקליהן תחילה. אחר כך עובר על הקשתות מהקשת המינימלית עד לקשת הגדולה ביותר במשקלה, ומוסיף כל קשת לעץ הפורש כל עוד לא הוספתה לא יוצרת מעגל בגרף המתקבל.
תת הגרף שמתקבל לבסוף הוא עץ פורש מינימלי.

האלגוריתם הוא חמדן, כיוון שבכל צעד נבחרת הפעולה הנראית אופטימלית באותו שלב - נוטלים את הקשת שמשקלה הקטן ביותר.

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

פסאודו קוד
הקוד הבא מסתמך על מבנה נתונים לאיחוד קבוצות זרות:

 KRUSKAL(G):
 1 A = ∅
 2 foreach v ∈ G.V:
 3   MAKE-SET(v)
 4 foreach (u, v) ordered by weight(u, v), increasing:
 5    if FIND-SET(u) ≠ FIND-SET(v):
 6       A = A ∪ {(u, v)}
 7       UNION(FIND-SET(u), FIND-SET(v))
 8 return A

דוגמה

ראו גם
 האלגוריתם של פרים
 מצגת הסבר על האלגוריתם של קרוסקל

קישורים חיצוניים

קרוסקל