שאלה לגבי BFS

מנהל: TA_Isana

שאלה לגבי BFS

הודעהעל ידי tagels » 13:59 16/07/2010

למה בעצם אנחנו צובעים בסוף את הקודקוד שהוצאנו מהתור לשחור?
יכלנו גם להשאיר אותו אפור, לא?
(באלגוריתם אני לא רואה שיש תנאי כלשהו שבודק האם הקודקוד אפור או שחור...)

פספסתי משהו?
תודה!
tagels
 
הודעות: 4
הצטרף: 21:14 30/10/2009

Re: שאלה לגבי BFS

הודעהעל ידי eliorar » 14:18 16/07/2010

כן, בעיקרון אין שום התייחסות לזה באלגוריתם, לפי מה שכתוב בהרצאה, אפור - קודקוד שגילינו אבל עוד לא סיימנו לטפל בו, כלומר עברנו על כל השכנים שלו ואפשר להמשיך הלאה. קודקוד אפור זה קודקוד שנמצא בתור. הוא הופך לשחור אחרי שהוצאנו אותו מהתור.
לדעתי זה די מוסתר באלגוריתם, כי כשאנחנו עוברים לטפל בקודקוד הבא אנחנו עוברים לטפל בקודקוד אפור (ולא בשחור), שזה בעצם הקודקוד הבא שנמצא בתוך התור. 
שים לב שלפני שאנחנו מכניסים קודקוד לתור, אנחנו מוודאים שהוא אפור..
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

Re: שאלה לגבי BFS

הודעהעל ידי ronenhe » 15:33 16/07/2010

יש מצב שזכרוני מטעה אותי אבל אנחנו מכניסים לתור/ מחסנית רק קודקודים לבנים.. ברגע שהוא ייכנס לתור נשנה את הצבע שלו לאפור.
יש מצב מאוד גדול שאני טועה אבל אני חושב שאני צודק במקרה הזה.. ואז כשמוציאים קודקוד מהתור/ מחסנית קודקוד הוא נצבע בשחור..
הצבעים הם בעצם אינדיקציה למצב עבודה עם קודקוד..
לבן- עוד לא הגענו אליו
אפור- בשלבי עבודה
שחור סיימנו עבודה
בעיקרון אין חשיבות לצביעת הקודקוד בשחור שכן גם קודקודים אפורים לא נכניס לתור/מחסנית (כי הוא כבר בפנים)
בכוונה אמרתי תור/מחסנית כי זה נכון גם לBFS וגם ל DFS
בהצלחה!
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009


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

מי מחובר

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