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