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

1. המטרה

נתון התיאור הבא לרשת תקשורת בו כל שורה מציגה נתב ברשת ורשימת מזהים של נתבים שהוא מחובר אליהם:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

בקלט הדוגמא נתב 0 מחובר לנתב מספר 2, נתב 2 מחובר בתורו לנתבים 0, 3 ו-4 וכך הלאה. למרות שאין חיבור ישיר בין 0 ל-4 ברור שאפשר להגיע מ-0 ל-4 אם עוברים דרך 2.

השאלה הראשונה היא לכמה נתבים ברשת אפשר להגיע אם מתחילים בנתב 0?

החלק השני- ניקח את כל הנתבים שאפשר להגיע אליהם כשמתחילים מ-0 ונקרא להם קבוצה. הקבוצה כוללת את כל הנתבים ברשת מלבד נתב מספר 1 אליו אי אפשר להגיע. לכן ניקח את 1 ונקרא לו קבוצה נוספת. השאלה היא כמה קבוצות כאלה יש ברשת?

אגב אם זה נראה לכם מוכר אתם בחברה טובה. השאלה לקוחה מכאן:

http://adventofcode.com/2017/day/12

2. איך למצוא מי מחובר לאן

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

המנגנון נקרא BFS והקוד בפייתון נראה כך:

from collections import defaultdict, deque

class Graph:
    def init(self, lines):
        self.data = defaultdict(set)

        for line in lines:
            line = line.strip()
            left, right = line.split(' <-> ')
            members = set([left] + right.split(', '))
            for src in members:
                for dst in members:
                    self.data[src].add(dst)

    def bfs(self, start):
        visited = set()
        q = deque()
        q.append(start)
        visited.add(start)

        while len(q) > 0:
            node = q.pop()
            for neighbor in self.data[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)

        return visited

g = Graph()

with open('datastructures_lab_3.txt') as f:
    g.init(f)
    neighbors = g.bfs('0')
    print(len(neighbors))

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

s = set()
group_count = 0
for item in g.data:
    if item not in s:
        s.update(g.bfs(item))
        group_count += 1

print(group_count)

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