שאלה לגבי DFS

מנהל: TA_Isana

שאלה לגבי DFS

הודעהעל ידי eliorar » 23:29 16/07/2010

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

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

Re: שאלה לגבי DFS

הודעהעל ידי eliorar » 13:41 17/07/2010

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

זה נכון?
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד