מימוש (חלק 2)
שיעור 6 מתוך 9 בקורס האלגוריתם של פרים – אלגוריתמים על גרפים של Coddy.
עכשיו גדלו את העץ, והוסיפו תמיד את הקשת החוצה הזולה ביותר.
אתגר
בינוניעכשיו בנו את העץ כולו.
כתבו פונקציה בשם prim שמקבלת את n ואת מערך edges השטוח (שלשות, לא מכוון) של גרף קשיר, ומחזירה את המשקל הכולל של העץ הפורש המינימלי, כשהעץ מתחיל בקודקוד 0.
שמרו דגל inTree לכל קודקוד. בכל סבב, מצאו את הקשת הזולה ביותר שיש לה בדיוק קצה אחד בעץ, הוסיפו את משקלה והכניסו את הקצה החיצוני שלה לעץ.
נסו בעצמכם
#include <stdlib.h>
int prim(int n, int* edges, int edges_size) {
// כתבו כאן קוד
return 0;
}
בחנו את עצמכםהשיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.
כל השיעורים ביחידה האלגוריתם של פרים – אלגוריתמים על גרפים
תרגלו בעצמכם: קומפיילר C אונליין