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

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

נלקח מויקיפדיה

הגדרות נוספות הקשורות להאלגוריתם של קרוסקל:
•אלגוריתמים בתורת הגרפים