מבוא

ברוכים הבאים לקורס האחרון בסדרת אלגוריתמים על גרפים! כמו Kruskal, האלגוריתם של Prim בונה עץ פורש מינימלי: קבוצת הקשתות הזולה ביותר שמחברת כל קודקוד בלי ליצור מעגל. שני האלגוריתמים מגיעים לאותה תוצאה בדרכים שונות.

Prim מרחיב את העץ כלפי חוץ מקודקוד התחלתי. בכל שלב הוא מוסיף את הקשת הזולה ביותר שמחברת את העץ לקודקוד שעדיין לא נמצא בו.

הגרף אינו מכוון ומשוקלל, ונתון באמצעות n (קודקודים 0 עד n - 1) ו-edges, מערך שטוח של שלשות [u0, v0, w0, ...] עבור קשת לא מכוונת u - v במשקל w. נתחיל מקודקוד 0.

בואו נסיים את הסדרה!