|
|
עמוד:251
נתון הגרף . G- ( V , E ) בשיטה הזאת נתחיל את הסריקה מאחד הקדקודים בגרף , הנקרא קדקוד מקור , ונסמן אותו . 5-ב המטרה היא לטייל על-פני הקשתות מקדקוד לקדקוד של הגרף כך שנבקר בכל קדקוד של הגרף ונבצע בו עיבוד כלשהו פעם אחת בלבד . שיטת הסריקה הזאת תתבצע כדלהלן מחלקים את קדקודי הגרף לשכבות באופן הזה 1 בשכבה 1 יהיו קדקודים שניתן להגיע אליהם מקדקוד המקור , S בעזרת מסלול שאורכו . 1 בשכבה 2 יהיו קדקודים שניתן להגיע אליהם מקדקוד המקור , 5 בעזרת מסלול שאורכו . 2 ובאופן כללי ן בשכבה , / לכל , / > 1 יהיו קדקודים כך שניתן להגיע אליהם מקדקוד המקור , S בעזרת מסלול שאורכו . / בשלב הראשון של האלגוריתם הנדון מבקרים בכל הקדקודים השייכים לשכבה הראשונה . בשלב השני של האלגוריתם מבקרים בכל הקדקודים השייכים לשכבה השנייה . נמשיך בביקור בקדקודי הגרף עד שנבקר בכל קדקודי הגרף פעם אחת בלבד . נדגיש כי האלגוריתם הנדון מבקר בכל קדקודי הגרף השייכים לשכבה , K לפני שמבקרים ( מגלים ) קדקוד כלשהו השייך לשכבה . K + 1 נדגים את התהליך שתואר לעיל על הגרף שלהלן י נניח שהקדקוד שממנו מתחילים את הסריקה הוא הקדקוד A הקדקוד A שייך לשכבה , 0 כיוון שאורך המסלול מצומת A לעצמו הוא . 0 עתה נבחר בכל הקשתות הנוגעות לקדקוד A והמובילות לקדקודים שעדיין לא ביקרנו בהם . בדוגמה שלנו , הקשת { A , B ) מובילה לקדקוד B שעדיין לא ביקרנו בו , והקשת ( A , Q מובילה לקדקוד B שעדיין לא ביקרנו בו .
|
|