מימוש (חלק 1)
שיעור 5 מתוך 9 בקורס האלגוריתם של פרים – אלגוריתמים על גרפים של Coddy.
נתחיל מהקשת הזולה ביותר היוצאת מקודקוד, המהלך הראשון של Prim.
אתגר
קלהמהלך הראשון של Prim הוא לבדוק את הקשתות היוצאות מקודקוד ההתחלה. בואו נבנה חיפוש כזה.
כתבו פונקציה בשם minEdgeFrom שמקבלת את המערך השטוח edges (שלשות [u, v, w, ...], לא מכוון) וקודקוד node, ומחזירה את המשקל הקטן ביותר מבין כל הקשתות שנוגעות ב־node. אם אין ל־node קשתות, החזירו -1.
לדוגמה, minEdgeFrom([0,1,5, 0,2,3, 1,2,1], 0) מחזירה 3.
נסו בעצמכם
#include <stdlib.h>
int minEdgeFrom(int* edges, int edges_size, int node) {
// כתבו כאן קוד
return -1;
}
בחנו את עצמכםהשיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.
כל השיעורים ביחידה האלגוריתם של פרים – אלגוריתמים על גרפים
תרגלו בעצמכם: קומפיילר C אונליין