מבני נתונים ומבוא לאלגוריתמים

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

ייצוג גרפים

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

גרף: אוסף של צמתים (קודקודים) וקשתות המחברות ביניהם.

צומת: יחידה בסיסית בגרף, המייצגת ישות (לדוגמה, עיר, אדם, שרת).

קשת: חיבור בין שני צמתים, המייצג קשר או יחס ביניהם.

גרף מכוון: גרף שבו לקשתות יש כיוון (לדוגמה, כביש חד-סטרי).

גרף לא מכוון: גרף שבו לקשתות אין כיוון (לדוגמה, כביש דו-סטרי).

מטריצת סמיכויות

מטריצה בגודל V x V (כאשר V הוא מספר הצמתים), שבה תא (i, j) מכיל 1 אם קיימת קשת מהצומת i לצומת j, ו-0 אחרת. בגרף לא מכוון, המטריצה סימטרית.

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

רשימת סמיכויות

מערך של רשימות מקושרות (או רשימות דינמיות). לכל צומת i, קיימת רשימה המכילה את כל הצמתים j שיש אליהם קשת מ-i.

יתרונות: דורש זיכרון של O(V + E) (כאשר E הוא מספר הקשתות), יעיל לגרפים דלילים, איטרציה על שכני צומת דורשת O(deg(v)).
חסרונות: בדיקת קיום קשת דורשת O(deg(v)) במקרה הגרוע.

אלגוריתמי מעבר בגרפים

אלגוריתמי מעבר מאפשרים לנו לבקר באופן שיטתי בכל הצמתים והקשתות בגרף. שני האלגוריתמים המרכזיים הם חיפוש לרוחב (BFS) וחיפוש לעומק (DFS).

חיפוש לרוחב (BFS)

מתחיל מצומת נתון ומבקר בכל שכניו הישירים, לאחר מכן בכל שכני השכנים, וכן הלאה, שכבה אחר שכבה. משתמש במבנה נתונים מסוג

תור: מבנה נתונים מסוג FIFO (First-In, First-Out).

שימושים: מציאת המסלול הקצר ביותר בגרף לא משוקלל, מציאת רכיבי קשירות.

חיפוש לעומק (DFS)

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

מחסנית: מבנה נתונים מסוג LIFO (Last-In, First-Out).

(או רקורסיה, המשתמשת במחסנית הקריאות).

שימושים: זיהוי מחזורים, מיון טופולוגי, מציאת רכיבי קשירות חזקים, בדיקת קשירות.

חיפוש לרוחב (BFS)

עקרונות פעולה:

מתחיל מצומת מקור S.
שומר תור של צמתים לבדיקה.
מסמן צמתים שביקר בהם כדי למנוע ביקורים חוזרים ולולאות אינסופיות.

שלבי האלגוריתם:

הכנס את צומת המקור S לתור וסמן אותו כ"ביקר".
כל עוד התור אינו ריק:
- הוצא צומת V מהתור.
- עבור על כל השכנים U של V:
  - אם U לא סומן כ"ביקר":
    - סמן את U כ"ביקר".
    - הכנס את U לתור.

תכונות וסיבוכיות:

BFS מבטיח למצוא את המסלול הקצר ביותר (במונחי מספר קשתות) מצומת המקור לכל צומת אחר בגרף לא משוקלל. סיבוכיות זמן: O(V+E) עבור רשימת סמיכויות, O(V^2) עבור מטריצת סמיכויות. סיבוכיות מקום: O(V) במקרה הגרוע (כאשר כל הצמתים נמצאים בתור).

חיפוש לעומק (DFS)

עקרונות פעולה:

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

שלבי האלגוריתם (רקורסיבי):

פונקציה DFS(צומת V):
- סמן את V כ"ביקר".
- עבור על כל השכנים U של V:
  - אם U לא סומן כ"ביקר":
    - קרא ל-DFS(U).

תכונות וסיבוכיות:

DFS שימושי לזיהוי רכיבי קשירות, איתור מחזורים, ומיון טופולוגי. סיבוכיות זמן: O(V+E) עבור רשימת סמיכויות, O(V^2) עבור מטריצת סמיכויות. סיבוכיות מקום: O(V) במקרה הגרוע (עומק הרקורסיה או גודל המחסנית).

יישומים ודגשים לבחינה

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

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

יישומים נפוצים:

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

שאלות לדיון

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

נקודות לתשובת מודל

ייצוג גרפים: רשימת סמיכויות עדיפה לגרפים דלילים (E <
BFS למסלול קצר: BFS מוצא את המסלול הקצר ביותר באופן טבעי בגרף לא משוקלל. כדי לשחזר את המסלול, יש לשמור עבור כל צומת את "האבא" שלו (predecessor) – הצומת שממנו הגענו אליו לראשונה. לאחר מכן, ניתן לשחזר את המסלול על ידי חזרה מהיעד לאחור דרך האבות עד שמגיעים למקור.
זיהוי מחזורים ב-DFS: בגרף מכוון, מחזור מזוהה כאשר במהלך DFS, אנו נתקלים בצומת שכבר נמצא במחסנית הרקורסיה הנוכחית (כלומר, צומת שביקרנו בו והוא עדיין לא סיים את עיבודו). נדרשים שני סוגי סימונים: "ביקר" (visited) ו"במהלך עיבוד" (in_recursion_stack או visiting). אם נתקלים בצומת "במהלך עיבוד", קיים מחזור.
בחירת אלגוריתם לרשת תקשורת: היינו משתמשים ב-BFS. מכיוון שכל "קפיצה" (קשת) שווה במשקלה, BFS מבטיח למצוא את המסלול בעל מספר הקשתות המינימלי (המסלול הקצר ביותר) מצומת המקור ליעד. DFS לא מבטיח זאת, שכן הוא מעמיק תחילה ועלול למצוא מסלול ארוך יותר לפני שימצא את הקצר ביותר.

מצאתם טעות או שחסר משהו?