|
|
עמוד:281
קל לראות , שכאשר מריצים את אלגוריתם DFS-n או את אלגוריתם BFS-n על עץ , מקבלים עץ פורש זהה , פרט לסדר הביקור בקדקודיו . אלגוריתם נוסף לסריקה לעומק באלגוריתם הזה מתבצעת צביעת הקדקודים כדי לציין את מצבם . כל קדקוד נצבע באחד מבין הצבעים : לבן , שחור ואפור . בתחילת האלגוריתם כל קדקוד יהיה צבוע בצבע לבן . כאשר קדקוד מתגלה , כלומר מגיעים אליו תוך כדי הסריקה , הוא נצבע בצבע אפור . כאשר אנו מסיימים את הטיפול בקדקוד ( עוזבים אותו ולא חוזרים אליו , ( אז הקדקוד נצבע בצבע שחור . נגדיר ? . d [ u ] מציין את מועד הגילוי של הקדקוד u בעת הסריקה . /[«] מציין את מועד סיום הטיפול בקדקוד u בעת הסריקה . ברור כי : d ( u ) <_/(«) כמל כן , ברור כי צבע הקדקוד , « לכל קדקוד , 14 & V יהיה לבן לפני הזמן , d [ u ] אפור נין הזמן d [ u ] לבין , /[«] ושחור אחרי הזמן . j \ u \ להלן האלגוריתם DFS ( G ) . 1 עבור כל קדקוד u e v color [«] < - white 1 . 1 : yyj p [ u ] < - NULL 1 . 2 */) בהתחלה כל הקדקודים צבועים בצבע לבן ולאף (/* */) אחד מהם אין הורה (/* */) time < r- 0 . 2 השעון מתחיל לתקתק (/* . 3 עבור כל קדקודי « 6 בצע אם color [«] הוא צבע לבן אז בצע : DFS _ Visit («)
|
|