פעולות של אלגוריתם Kruskal
מבנה
נתונים ואלגוריתמים
רצף הדיאגרמות
הבא ידגים את אלגוריתם Kruskal
על פי פעולות:
|
gh הינו הקצר ביותר g או h
יכולים להיות הנציגים, g
נבחר שרירותית |
|
ci יוצר שני עצים. c נבחר כנציג עבור השני. |
|
fg הינו הקצר ביותר הבא בתור. הוסף
אותו, בחר את g
כנציג. |
|
ab יוצר את העץ השלישי. |
|
הוסף
את cf, מזג
את שני העצים. c נבחר כנציג. |
|
gi הינו הזול ביותר הבא בתור, אך
הוא יוצר מעגל. c הינו הנציג עבור שניהם. |
|
הוסף
את cd
במקום זאת |
|
hi יצור מעגל. |
|
הוסף
את ah
במקום זאת. |
|
bc יצור מעגל. הוסף
את de
במקום זאת על
מנת להשלים את עץ ההיקף - כל
העצים מקושרים, c
הינו נציג בודד. |
חזור ל: עצים פורשים
מינימליים חזור
ל: תוכן עניינים