איך אפשר לשנות את הקוד של DFS, כך שידפיס את כל קשת בגרף מכוון G ביחד עם סוגה (כלומר קשת אחורית/קדימה/עץ/חוצה)?
יש קשר למשפט הסוגריים שלמדנו, אבל אני לא מצליח ליישם את זה באלגוריתם..
כלומר קשת (u,v) היא קדימה אמ"ם d≤d[v]≤f[v]≤f - כאשר u הוא אב קדמון של v. (קשת מאבא לצאצא)
קשת אחורית אמ"ם d[v]≤d≤f≤f[v] - כאשר v אב קדמון של u (קשת מצאצא לאבא)
וכו'
איך אני בעצם יכול לדעת מי יוצא לפני מי באלגוריתם?
הכיוון שלי היה:
בלולאה של ה DFS-VISIT לבדוק אם הגעתי לקודקוד אפור ואז: לפי זמני ההתחלה לבדוק, אם לקודקוד שאני מבקר בו זמן התחלה קטן משלי אז אני בצלע אחורית,
אם הגעתי לקודקוד אפור ואני רואה שזמן ההתחלה שלי קטן וזה של האפור אז אני בצלע קדמית.. אני לא כל כך בטוח, אשמח אם מישהו יחזק את הטענה שלי/או ימצא דרך נכונה אם זו לא..
שאלה לגבי DFS
מנהל: TA_Isana
Re: שאלה לגבי DFS
אוקיי נראה לי שיש לי תשובה:
קשת עץ (הרגילות): אם עברנו מאפור ללבן - כל גילוי של קודקוד חדש.
קשת אחורית: מאפור u לאפור v, כך ש u צאצא ו v אב קדמון, כלומר נבדוק אם שניהם אפורים וגם d >d[v]
קשת קדמית: מאפור לשחור, כלומר אם u אב קדמון ו v צאצא אז d<d[v]
קשת חוצה: גם פה זה מאפור לשחור אבל d>d[v]
זה נכון?
קשת עץ (הרגילות): אם עברנו מאפור ללבן - כל גילוי של קודקוד חדש.
קשת אחורית: מאפור u לאפור v, כך ש u צאצא ו v אב קדמון, כלומר נבדוק אם שניהם אפורים וגם d >d[v]
קשת קדמית: מאפור לשחור, כלומר אם u אב קדמון ו v צאצא אז d<d[v]
קשת חוצה: גם פה זה מאפור לשחור אבל d>d[v]
זה נכון?