ראשי > עצים פורשים > האלגוריתם של קרוסקל

האלגוריתם של קרוסקל

תאור האלגוריתם

האלגוריתם של קרוסקל הוא האלגוריתם הראשון שנראה למציאת עצים פורשים. מהלך האלגוריתם הוא פשוט, בכל שלב נבחר את הקשת בעלת המשקל המינימלי מבין כל הקשתות שנותרו בגרף ונחבר אותה לאחד העצים בתנאי שהיא אינה יוצרת מעגל. האלגוריתם נעצר כאשר בנינו עץ עם V-1 קשתות או כאשר סיימנו עם כל הקשתות בגרף.

האלגוריתם של קרוסקל שייך למשפחת ה אלגוריתמים החמדניים, מאחר ובכל שלב הוא בוחר את הקשת בעלת המשקל המינימלי ביותר.

פסאודו קוד

1. T= {}

2. while ( T has < V-1 edges and E not empty ) {

3.    pick (u,v) from E such that its weight is minimal

4.    delete (u,v) from E

5.    if adding (u,v) doesn't create a cycle, add it to T

6. }

הסבר:

T היא קבוצת הקשתות שתהווה את הפתרון הסופי. האלגוריתם נעצר (שורה 2) כאשר T מכיל V-1 קשתות. מאחר ונדאג בכל שלב של שלמות העץ (שורה 5) אנו יכולים להניח שאם ברשותינו V-1 קשתות הרי שיש לנו עץ המחבר V קודקודים.

בכל שלב בלולאה, ניקח את הקשת בעלת המשקל המינימלי מהקשתות שנותרו (שורה 3) ונמחק אותה מהגרף (שורה 4). אם אפשר לחבר קשת זו לעץ מבלי ליצור מעגל (שורה 5) נוסיף אותה ליער המתהווה.

דוגמת הרצה