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