|
|
עמוד:337
בכל שלב של האלגוריתם של קרוסקל , פרט לשלב האחרון , אנו מקבלים יער . כל רכיב הנו קבוצה של קדקודים , והרכיבים הס זרים זה לזה . משום כך יש צורך לייצג את היער באמצעות מבנה נתונים המייצג קבוצות זרות של איברים . כל קבוצה תכיל את קדקודיו של עץ אחד ביער . על מבנה הנתונים הזה נגדיר את הפעולות הבסיסיות שלהלן ו - MAKE-SET ( v ) יצירת קבוצה בת איבר אחד . - FIND ( v ) פעולה זו מחזירה את מספר הקבוצה ( רכיב קשירות ) שאליה שייך הקדקוד ע . - UNION ( H , 1 ' ) פעולה זו מקבלת שני קדקודים u 1-ו וגורמת לאיחוד שני הרכיבים המכילים קדקודים אלו לרכיב קשירות אחת . בנוסף , נגדיר את הפעולה הבאה ( על קשתות הגרף ? . ( - SORT ( £ ) פעולה זו ממיינת את הקשתות לפי סדר יורד , על סמך המשקלות שעליהן . לאור האמור לעיל , לפניך המימוש של האלגוריתם של קרוסקל . נתון הגרף . G = ( V , E ) המטרה היא לבנות עץ פורש מינימלי . T = { V , E ) T KRUSKAL ( G ) // PRE-ALGORITHM L < - SORT ( £ ) for each ve Vdo MAKE-SET ( v ) E ^§ // GROW TREE for each ( u , v ) e Ldo u < - FIND ( w ) v' < - FIND ( v ) if u' it v' then E <^ E u {( u , v )}
|
|