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