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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

כלומר, המטרה היא למצוא תת קבוצה של הקשתות שתיצור עץ המכיל את כל הקודקודים המקוריים, כאשר סכום משקלי הקשתות בתת-קבוצה זו הינו מינימלי.

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

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

סיבוכיות האלגוריתם מושפעת בעיקר מהצורך למיין את הקשתות בתחילת הפעלתו, ועל כן היא חסומה על ידי \ O(E \log E) \le O(E \log (V^2)) = O(E \log V) במקרה הכללי – הסיבוכיות המינימלית למיון מבוסס השוואות של \ E איברים, כאשר \ E הוא מספר הקשתות בגרף. עם זאת, במקרה והקשתות כבר ממויינות או שניתן למיין אותן בזמן לינארי, זמן הריצה יהיה \ \Theta(E\ \alpha(E,V)).

פסאודו קוד[עריכת קוד מקור | עריכה]

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

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(u, v)
8 return A

דוגמה[עריכת קוד מקור | עריכה]

תמונה תיאור
Prim Algorithm 0.svg זה הגרף המקורי שלנו. המספרים ליד הקשתות מציינים את משקלן, אף קשת לא מודגשת.
Kruskal Algorithm 1.svg הקשתות AD ו-CE שמשקלן 5 הן הקלות ביותר. AD נבחרה באופן שרירותי והודגשה.
Kruskal Algorithm 2.svg כעת CE שמשקלה 5 היא הקשת הקלה ביותר שאינה סוגרת מעגל, ולכן מודגשת.
Kruskal Algorithm 3.svg הקשת הקלה ביותר הבאה שאינה סוגרת מעגל היא DF שמשקלה 6.
Kruskal Algorithm 4.svg כעת הקשתות הקלות ביותר הן AB ו-BE שאורכן 7. AB נבחרת באופן שרירותי ומודגשת. הקשת BD נצבעת באדום כיוון שכבר קיים מסלול בין B ל-D (בירוק), ולכן היא תיצור מעגל (ABD) אם תיבחר.
Kruskal Algorithm 5.svg התהליך ממשיך ו-BE נצבעת בירוק. בשלב זה מספר קשתות נצבעות באדום: BC (כי היא תיצור את המעגל BCE), הקשת DE (כי היא תיצור את המעגל DEBA), ו-EF (שתיצור את המעגל FEBAD).
Kruskal Algorithm 6.svg לבסוף, התהליך מסתיים עם בחירת הקשת EG שמשקלה 9, ומציאת עץ פורש מינימלי (בירוק).

ראו גם[עריכת קוד מקור | עריכה]