האלגוריתם של קרוסקל
האלגוריתם של קרוסקל הוא אלגוריתם חמדן לפתרון בעיית מציאת עץ פורש מינימלי בגרף ממושקל קשיר לא מכוון, שתואר לראשונה במאמר של ג'וזף קרוסקל בשנת 1956. המטרה היא למצוא תת קבוצה של הקשתות שתיצור עץ המכיל את כל הקודקודים המקוריים, כאשר סכום משקלי הקשתות בתת-קבוצה זו הינו מינימלי.
לפי אלגוריתם זה, כדי לבחור את הקשתות שיימצאו בעץ פורש מינימלי, יש למיין לפי משקליהן תחילה. אחר כך יש ליטול לפי הסדר קשת אחר קשת ולהוסיפה לתת הגרף, מהקשת המינימלית עד לקשת הגדולה ביותר במשקלה, כל עוד לא ייווצר מעגל בגרף המתקבל. תת הגרף שמתקבל לבסוף הוא עץ פורש מינימלי.
האלגוריתם הוא חמדן, כיוון שבכל צעד נבחרת הפעולה הנראית אופטימלית באותו שלב - נוטלים את הקשת שמשקלה הקטן ביותר.
סיבוכיות האלגוריתם מושפעת בעיקר מהצורך למיין את הקשתות בתחילת הפעלתו. בגרף עם קבוצת קודקודים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} וקבוצת קשתות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} הסיבוכיות תהיה חסומה על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(|E|\log|E|) = O(|E| \log |V|)} במקרה הכללי, הסיבוכיות המינימלית למיון מבוסס השוואות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |E|} איברים. עם זאת, במקרה והקשתות כבר ממויינות או שניתן למיין אותן בזמן לינארי (לדוגמה מיון בסיס כשהמשקלים קטנים), על ידי שימוש במבנה נתונים של איחוד קבוצות זרות זמן הריצה יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Theta(|E|\ \alpha(|V|))} כש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha(|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
דוגמה
| תמונה | תיאור |
|---|---|
| שגיאה ביצירת תמונה ממוזערת: | זה הגרף המקורי שלנו. המספרים ליד הקשתות מציינים את משקלן, אף קשת לא מודגשת. |
| שגיאה ביצירת תמונה ממוזערת: | הקשתות AD ו-CE שמשקלן 5 הן הקלות ביותר. AD נבחרה באופן שרירותי והודגשה. |
| קובץ:Kruskal Algorithm 2.svg | כעת CE שמשקלה 5 היא הקשת הקלה ביותר שאינה סוגרת מעגל, ולכן מודגשת. |
| שגיאה ביצירת תמונה ממוזערת: | הקשת הקלה ביותר הבאה שאינה סוגרת מעגל היא 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, ומציאת עץ פורש מינימלי (בירוק). |
ראו גם
קישורים חיצוניים
האלגוריתם_של_קרוסקל21269170Q797860