שיעור 14: גרפים — BFS ו-DFS

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

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

סריקת גרף: ביקור שיטתי בכל הצמתים שניתן להגיע אליהם מצומת התחלה, באמצעות BFS (תור) או DFS (מחסנית/רקורסיה).
מילון שכנויות: ייצוג גרף שבו כל צומת ממופה לרשימת השכנים שלו: {node: [neighbors]} — גישה לשכנים ב-O(1).
קבוצת ביקור: קבוצה (set) שמסמנת אילו צמתים כבר נסרקו, כדי לא לבקר בהם שוב ולמנוע לולאות אינסופיות.