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

1. מה זה גרף?

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

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

אז אם ניקח לדוגמא את האותיות באנגלית A-F ונסדר אותן במערך זה יראה בערך כך:

[A] - [B] - [C] - [D] - [E] - [F]

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

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

    B - - - E
   /        /
  /       /
A - - - F
  \
   \
    C - - - D

כאן אנחנו אומרים ש A מקושרת ל C, F ו B. ש E מקושרת ל B ו- F וש C מקושרת ל D ול A.

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

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

2. סריקת גרף

מבני נתונים טובים בשביל לענות על שאלות, אבל על איזה שאלות יכול גרף לענות? סוג אחד של שאלות קשור ליכולת להגיע ממקום למקום בגרף: האם שני צמתים מחוברים? האם אפשר להגיע מצומת A לצומת E? כמה צמתים צריך לעבור כדי להגיע מ E ל A? ומה הדרך הכי מומלצת?

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

1. אנחנו לא תמיד זוכרים מי כל הצמתים שיצרנו.

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

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

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

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

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

.
├── one
├── three
│   ├── five
│   ├── four
│   └── two
│       └── one
└── two
    ├── twenty-one
    │   └── a.txt
    └── twenty-two

ואני אפעיל find אני אקבל:

.
./three
./three/two
./three/two/one
./three/five
./three/four
./one
./two
./two/twenty-two
./two/twenty-one
./two/twenty-one/a.txt

ואנחנו רואים איך find התחיל עם צומת אחת three, ממנה המשיך לחקור כמה שרק יכל והגיע לילדים של three שהן התיקיות two ובתוכה one, ואז הלך אחורה לילדים הבאים בתור של three.

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

אם find היתה מאפשרת סריקת רוחב היא כנראה היתה מחזירה רשימה שנראית כך:

.
./three
./one
./two

./three/two
./three/five
./three/four
./two/twenty-two
./two/twenty-one

./three/two/one
./two/twenty-one/a.txt

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

3. מימוש גרף בשפת Python

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

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

הקוד למחלקה עם הפעולה בשפת Python יהיה בסך הכל:

class Node:
    def __init__(self, value):
        self.neighbours = []
        self.value = value

    def connect_to(self, other_node):
        if other_node not in self.neighbours:
            self.neighbours.append(other_node)
            other_node.connect_to(self)

ואפשר להשתמש בו בקלות כדי ליצור גרף:

n1 = Node('A')
n2 = Node('B')
n1.connect_to(n2)

4. סריקת הגרף בשיטת BFS

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

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

2. שימו צומת אחד על התור וצאו לדרך.

3. כל עוד יש צומת בתור:

4. תוציאו את הצומת הראשון מהתור. אם כבר ביקרתם בו תזרקו הצידה וחיזרו ל-3.

5. סמנו לעצמכם שביקרתם בו, והדפיסו אותו (או תעשו מה שאתם צריכים איתו - זה לא משנה).

6. עכשיו קחו את כל השכנים המיידיים שלו והכניסו גם אותם לתור.

7. חיזרו ל-3.

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

אם אתם לא לגמרי מצליחים לראות את זה בראש שווה להעיף מבט בקישור https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/ שמציע ויזואליזציה מדליקה שלב-אחרי-שלב של האלגוריתם.

בתרגום לקוד פייתון האלגוריתם יראה כך:

def bfs(q, callback):
    visited_nodes = set()
    while len(q) > 0:
        node = q.popleft()

        # Skip this node, we've already visited it
        if node in visited_nodes: continue

        # Now we can start processing the node:
        # 1. Let's notify outside code that we found a new node
        callback(node)

        # 2. Let's mark it as visited so we won't have to
        #    process it again
        visited_nodes.add(node)

        # 3. Let's add all of its neighbors to the queue
        #    so we'll be able to process them too
        for friend in node.neighbours:
            q.append(friend)

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

בשביל לראות את זה עובד יצרתי צמתים שמייצגים את עץ התיקיות מהדוגמא הקודמת ושלחתי אותם ל BFS:

root = Node('/')
n1 = Node('/one')
root.connect_to(n1)

n2 = Node('/two')
root.connect_to(n2)
n2.connect_to(Node('/two/twenty-two'))
n21 = Node('/two/twenty-one')
n2.connect_to(n21)
n21.connect_to(Node('/two/twenty-one/a.txt'))

n3 = Node('/three')
root.connect_to(n3)

n3.connect_to(Node('/three/five'))
n3.connect_to(Node('/three/four'))

n4 = Node('/three/two')
n3.connect_to(n4)
n4.connect_to(Node('/three/two/one'))


q = deque()
q.append(root)
bfs(q, lambda n: print(n.value))

קוד יצירת הצמתים אולי מסורבל, אבל התוצאה היא בדיוק מה שציפינו למצוא:

/
/one
/two
/three
/two/twenty-two
/two/twenty-one
/three/five
/three/four
/three/two
/two/twenty-one/a.txt
/three/two/one

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

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