ספירת רכיבים קשירים
שיעור 13 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.
רכיב קשיר הוא קבוצה מקסימלית של קודקודים שבה לכל זוג יש מסלול ביניהם. בגרף ללא קשתות יש מספר רכיבים השווה למספר הקודקודים שלו; בגרף קשיר לחלוטין יש בדיוק רכיב אחד.
כדי לספור אותם, עבור על כל הקודקודים. בכל פעם שאתה מוצא קודקוד שעדיין לא בוקר, זהו רכיב חדש: הגדל את המונה, ואז בצע BFS או DFS ממנו כדי לסמן כל קודקוד שניתן להגיע אליו כמבוקָר. המשך לקודקוד הבא שטרם בוקר.
האתגר הזה מספק לך גם את רשימת הקודקודים וגם את הקשתות, כי קודקודים מבודדים (ללא קשתות) עדיין נחשבים לרכיב בפני עצמם, ועלינו לדעת שהם קיימים.
אתגר
קלכתבו פונקציה countConnectedComponents שמקבלת מערך int דו־ממדי adjacency ומערך int vertices, ומחזירה את מספר הרכיבים הקשירים בגרף.
בנו את הגרף: תחילה קראו ל־addVertex עבור כל מפתח ב־vertices (כדי שגם קודקודים מבודדים יהיו קיימים), ואז קראו ל־addEdge עבור כל זוג ב־adjacency. לאחר מכן עברו על כל הקודקודים: כל קודקוד שלא בוקר מתחיל רכיב חדש (הגדילו את המונה), ואז בצעו ממנו DFS/BFS כדי לסמן את כל הרכיב שלו ככזה שבוקר.
חובה להשתמש במחלקה Graph (המסופקת ב־graph) — אל תשתמשו במבנים המובנים בשפה (מפות, קבוצות) כדי לייצג את רשימות השכנות. נתונים עזר לאלגוריתם (קבוצות קודקודים שבוקרו, מחסניות) יכולים להשתמש בטיפוסים של ספריית התקן.
נסו בעצמכם
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}
כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9
תרגלו בעצמכם: קומפיילר C אונליין