הצגת המקור של הדף "האלגוריתם של קרוסקל"

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

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

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

[[סיבוכיות]] האלגוריתם מושפעת בעיקר מהצורך למיין את הקשתות בתחילת הפעלתו. בגרף עם קבוצת קודקודים <math>V</math> וקבוצת קשתות <math>E</math> הסיבוכיות תהיה חסומה על ידי
<math>O(|E|\log|E|) = O(|E| \log |V|)</math> במקרה הכללי, הסיבוכיות המינימלית ל[[מיון (מדעי המחשב)|מיון]] מבוסס השוואות של <math>\ |E|</math> איברים. עם זאת, במקרה והקשתות כבר ממויינות או שניתן למיין אותן בזמן ליניארי (לדוגמה [[מיון בסיס]] כשהמשקלים קטנים), על ידי שימוש במבנה נתונים של [[איחוד קבוצות זרות]] זמן הריצה יהיה <math>\ \Theta(|E|\ \alpha(|V|))</math> כש-<math>\alpha(|V|)</math> היא הפונקציה ההופכית ל[[פונקציית אקרמן]] (פונקציה הגדלה לאט מאוד).

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

<div class="mw-content-ltr">
 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
</div>

== דוגמה ==

{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! תמונה !! תיאור
|-
|[[תמונה:Prim Algorithm 0.svg|200px]]
|זה הגרף המקורי שלנו. המספרים ליד הקשתות מציינים את משקלן, אף קשת לא מודגשת.
|-
|[[תמונה:Kruskal Algorithm 1.svg|200px]]
|הקשתות '''AD''' ו-'''CE''' שמשקלן 5 הן הקלות ביותר. '''AD''' נבחרה באופן שרירותי והודגשה.
|-
|[[תמונה:Kruskal Algorithm 2.svg|200px]]
|כעת '''CE''' שמשקלה 5 היא הקשת הקלה ביותר שאינה סוגרת מעגל, ולכן מודגשת.
|-
|[[תמונה:Kruskal Algorithm 3.svg|200px]]
|הקשת הקלה ביותר הבאה שאינה סוגרת מעגל היא '''DF''' שמשקלה 6.
|-
|[[תמונה:Kruskal Algorithm 4.svg|200px]]
|כעת הקשתות הקלות ביותר הן '''AB''' ו-'''BE''' שאורכן 7. '''AB''' נבחרת באופן שרירותי ומודגשת. הקשת '''BD''' נצבעת באדום כיוון שכבר קיים מסלול בין B ל-D (בירוק), ולכן היא תיצור מעגל ('''ABD''') אם תיבחר.
|-
|[[תמונה:Kruskal Algorithm 5.svg|200px]]
|התהליך ממשיך ו-'''BE''' נצבעת בירוק. בשלב זה מספר קשתות נצבעות באדום: '''BC''' (כי היא תיצור את המעגל '''BCE'''), הקשת '''DE''' (כי היא תיצור את המעגל '''DEBA'''), ו-'''EF''' (שתיצור את המעגל '''FEBAD''').
|-
|[[תמונה:Kruskal Algorithm 6.svg|200px]]
|לבסוף, התהליך מסתיים עם בחירת הקשת '''EG''' שמשקלה 9, ומציאת עץ פורש מינימלי (בירוק).
|}

==ראו גם==
* [[האלגוריתם של פרים]]
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

[[קטגוריה:אלגוריתמים בתורת הגרפים|קרוסקל]]