|
|
صفحة: 341
6 . 3 . 2 יעילות האלגוריתם של קתסקל זמן הריצה של האלגוריתם של קרוקסל , אשר פועל על גרף בלתי מכוון קשיר , G = { V , E ) תלוי במימוש מבנה הנתונים יער , שהוא קבוצות זרות . ייצוג קבוצות זרות על-ידי רשימות מקושרות כל קבוצה מיוצגת על-ידי רשימה מקושרת , והאיבר הראשון בכל רשימה משמש כנציג הקבוצה המיוצגת באמצעות הרשימה . התרשים שלהלן מתאר את הייצוג של שתי קבוצות זרות על-ידי שתי רשימות מקושרות ו בכל צומת ברשימה שלושה שדות עיקריים האחד - מצביע לצומת הבא המכיל איבר כלשהו של אותה קבוצה . השני - מכיל את שם האיבר . השלישי - מצביע לצומת הראשון ברשימה המכיל איבר שהוא הנציג של הקבוצה . שימו לב n הרשימה הראשונה מכילה את אברי הקבוצה , { a , b , c , d ) והרשימה השנייה מכילה את איברי הקבוצה ?{ e , f , g } . 2 לכל רשימה יש מצביע לראשה וגם לסופה . . 3 הרשימה המתקבלת מהפעולה Union ( b , g ) היא :
|
|