דף 1 מתוך 1

שאלה לגבי DFS

נשלח: 00:29 17/07/2010
על ידי eliorar
איך אפשר לשנות את הקוד של DFS, כך שידפיס את כל קשת בגרף מכוון G ביחד עם סוגה (כלומר קשת אחורית/קדימה/עץ/חוצה)?

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

Re: שאלה לגבי DFS

נשלח: 14:41 17/07/2010
על ידי eliorar
אוקיי נראה לי שיש לי תשובה:
קשת עץ (הרגילות): אם עברנו מאפור ללבן - כל גילוי של קודקוד חדש.
קשת אחורית: מאפור u לאפור v, כך ש u צאצא ו v אב קדמון, כלומר נבדוק אם שניהם אפורים וגם d >d[v]
קשת קדמית: מאפור לשחור, כלומר אם u אב קדמון ו v צאצא אז d<d[v]
קשת חוצה: גם פה זה מאפור לשחור אבל d>d[v]

זה נכון?