איך זה עובד?

שיעור 3 מתוך 9 בקורס האלגוריתם של קרוסקל - אלגוריתמים בגרפים של Coddy.

איחוד-חיפוש שומר מערך parent. כל קודקוד מתחיל כשורש של עצמו. שתי פעולות מניעות את הכול:

find(x): עוקבים אחר קישורי parent עד שמגיעים לשורש (קודקוד שהוא ההורה של עצמו). שני קודקודים מחוברים כאשר יש להם אותו שורש.
union(a, b): מצביעים משורש אחד אל האחר, וכך מאחדים את שתי הקבוצות.

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

לאחר עיבוד כל הקשתות, הקשתות שנבחרו יוצרות את ה-MST (בגרף קשיר, בדיוק n - 1 מהן).

נסו בעצמכם

השיעור הזה לא כולל אתגר קוד.