עמוד 1 מתוך 1

שאלה לגבי BFS

הודעהפורסם: 13:59 16/07/2010
על ידי tagels
למה בעצם אנחנו צובעים בסוף את הקודקוד שהוצאנו מהתור לשחור?
יכלנו גם להשאיר אותו אפור, לא?
(באלגוריתם אני לא רואה שיש תנאי כלשהו שבודק האם הקודקוד אפור או שחור...)

פספסתי משהו?
תודה!

Re: שאלה לגבי BFS

הודעהפורסם: 14:18 16/07/2010
על ידי eliorar
כן, בעיקרון אין שום התייחסות לזה באלגוריתם, לפי מה שכתוב בהרצאה, אפור - קודקוד שגילינו אבל עוד לא סיימנו לטפל בו, כלומר עברנו על כל השכנים שלו ואפשר להמשיך הלאה. קודקוד אפור זה קודקוד שנמצא בתור. הוא הופך לשחור אחרי שהוצאנו אותו מהתור.
לדעתי זה די מוסתר באלגוריתם, כי כשאנחנו עוברים לטפל בקודקוד הבא אנחנו עוברים לטפל בקודקוד אפור (ולא בשחור), שזה בעצם הקודקוד הבא שנמצא בתוך התור. 
שים לב שלפני שאנחנו מכניסים קודקוד לתור, אנחנו מוודאים שהוא אפור..

Re: שאלה לגבי BFS

הודעהפורסם: 15:33 16/07/2010
על ידי ronenhe
יש מצב שזכרוני מטעה אותי אבל אנחנו מכניסים לתור/ מחסנית רק קודקודים לבנים.. ברגע שהוא ייכנס לתור נשנה את הצבע שלו לאפור.
יש מצב מאוד גדול שאני טועה אבל אני חושב שאני צודק במקרה הזה.. ואז כשמוציאים קודקוד מהתור/ מחסנית קודקוד הוא נצבע בשחור..
הצבעים הם בעצם אינדיקציה למצב עבודה עם קודקוד..
לבן- עוד לא הגענו אליו
אפור- בשלבי עבודה
שחור סיימנו עבודה
בעיקרון אין חשיבות לצביעת הקודקוד בשחור שכן גם קודקודים אפורים לא נכניס לתור/מחסנית (כי הוא כבר בפנים)
בכוונה אמרתי תור/מחסנית כי זה נכון גם לBFS וגם ל DFS
בהצלחה!