פעולות של אלגוריתם Kruskal

מבנה נתונים ואלגוריתמים

 

 

רצף הדיאגרמות הבא ידגים את אלגוריתם Kruskal על פי פעולות:

 

 

gh הינו הקצר ביותר

g או h יכולים להיות הנציגים, g נבחר שרירותית

 

ci יוצר שני עצים.

 

c נבחר כנציג עבור השני.

 

fg הינו הקצר ביותר הבא בתור.

 

הוסף אותו, בחר את g כנציג.

 

 

 

ab יוצר את העץ השלישי.

 

 

 

הוסף את cf,

מזג את שני העצים.

 

c נבחר כנציג.

 

gi הינו הזול ביותר הבא בתור,

אך הוא יוצר מעגל.

 

c הינו הנציג עבור שניהם.

 

 

הוסף את cd במקום זאת

 

 

hi יצור מעגל.

 

 

 

הוסף את ah במקום זאת.

 

bc יצור מעגל.

 

הוסף את de במקום זאת

על מנת להשלים את עץ ההיקף -

כל העצים מקושרים, c הינו נציג בודד.

 

 

חזור ל: עצים פורשים מינימליים                            חזור ל: תוכן עניינים