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

BFS Algorithm

BFS (ראשי תיבות של Breadth First Search) - חיפוש לרוחב, הוא אלגוריתם המשתמש במבנה נתונים תור (Queue) על מנת לעבור ולהדפיס את הצמתים של עץ בינארי בצורה רוחבית (על פי הייצוג בעץ).

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

 

עקרון האלגוריתם:

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

 

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

1. BFS (t)
2. enqueue(q, t)
3. while (notEmpty (q)) do
4.     t <- dequeue(q)
5.     print (t)
6.     if (left(t) != NIL)
7.         enqueue (q, left(t))
8.     if (right(t) != NIL)
9.         enqueue (q, right(t))

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

  1. נקבל עץ בינארי: {a, b, c, d, e, f, g, h} לפי התמונה משמאל.
  2. שורה 2: נוסיף לתור q את השורש t (שקיבלנו בעת הקריאה לפונקציה - אלגוריתם), ז”א את a.
  3. שורה 3: כל עוד התור q אינו ריק (והוא אינו ריק מכיוון שיש לנו בו את a):
    • שורה 4: נוציא את האיבר הראשון מהתור (השורש, a), ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א a.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL. במקרה שלנו זה נכון, הבן השמאלי הוא b, וניכנס ל if:
      • שורה 7: נכניס את הבן השמאלי, b, לתור q.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, במקרה שלנו הוא c, ולכן ניכנס ל if:
      • שורה 9: נכניס את הבן הימני, c, לתור q.
    • כעת התור, q, נראה: [b, c].
  4. שורה 3: התור עדיין לא ריק, ולכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, b, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א b.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL. והוא שווה ל d, לכן ניכנס ל if:
      • שורה 7: נכניס את הבן השמאלי, d, לתור q.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL. והוא שווה ל e, לכן ניכנס ל if:
      • שורה 9: נכניס את הבן הימני, e, לתור q.
    • כעת התור q, נראה: [c, d, e].
  5. שורה 3: התור עדיין לא ריק, ולכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, c, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א c.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא f, לכן ניכנס ל if:
      • שורה 7: נכניס את הבן השמאלי, f, לתור q.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא g, לכן ניכנס ל if:
      • שורה 9: נכניס את הבן הימני, g, לתור q.
    • כעת התור, q, נראה: [d, e, f, g].
  6. שורה 3: התור עדיין לא ריק, לכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, d, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א d.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • כעת התור, q, נראה: [e, f, g].
  7. שורה 3: התור עדיין לא ריק, לכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, e, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א e.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא h, ולכן ניכנס ל If:
      • שורה 7: נכניס את הבן השמאלי, h, לתור q.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • כעת התור, q, נראה: [f, g, h].
  8. שורה 3: התור עדיין לא ריק, לכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, f, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א f.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • כעת התור, q, נראה: [g, h].
  9. שורה 3: התור עדיין לא ריק, לכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, g, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א g.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • כעת התור, q, נראה: [h].
  10. שורה 3: התור עדיין לא ריק, לכן נמשיך בלולאת ה while:
    • שורה 4: נוציא את האיבר הראשון מהתור, h, ונכניס אותו למשתנה t.
    • שורה 5: נדפיס את t, ז”א h.
    • שורה 6: נבדוק האם הבן השמאלי של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • שורה 8: נבדוק האם הבן הימני של t שונה מ NIL, הוא לא שונה, ולכן לא ניכנס ל If.
    • כעת התור, q, נראה: [ ].
  11. שורה 4: התור ריק, ולכן לא נמשיך בלולאת ה while.

 

סיבוכיות זמן ריצה: (O(n.
סיבוכיות מקום: (O(1.