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