אתגר תכנותי: מספר הרכיבים המחוברים בגרף לא מכוון

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

האתגר התכנותי

מספר רכיבים מחוברים בגרף לא מכוון

ישנו גרף לא מכוון הכולל n צמתים nodes. יש גם מערך המכיל קרנות edges, המתוארות באמצעות מערכים, כאשר:

edges[i] = [a, b]

פירושו שיש קרן המקשרת את צומת a לצומת b בגרף.

הצמתים ממוספרים מ-0 עד n - 1.

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

רעיונות מרכזיים בהבנת הבעיה

כדי לפתור זאת, אנו צריכים לכתוב קוד מחשב הסורק traverse את כל הצמתים השייכים לאותו רכיב מחובר connected component לפני שנעבור לרכיב הבא. כאן נכנס לתמונה הנושא החשוב של סריקת גרפים graph traversal, כולל:

אלגוריתם חיפוש לרוחב (BFS)

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

אלגוריתם חיפוש לעומק (DFS)

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

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

מקרי בוחן

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

# Tests
print(count_components(3, [[0,1], [0,2]]))   # Output: 1
print(count_components(6, [[0,1], [1,2], [2,3], [4,5]]))  # Output: 2
print(count_components(2, []))   # Output: 2
print(count_components(0, []))   # Output: 0

מדוע נבחרו המקרים האלה?

• 3 צמתים בגרף מחובר.
• גרף עשוי מ-2 רכיבים נפרדים: 0-1-2-3 ו- 4-5.
• גרף המכיל 2 צמתים מבודדים המהווים 2 רכיבים נפרדים.
• גרף ריק ללא צמתים.

טיפ ללומד

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

פתרון מבוסס DFS איטרטיבי

from collections import deque

def count_components(n, edges):
    adj_list = {node: [] for node in range(n)}
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)

    visited = set()

    def traverse(start):
        stack = deque([start])
        visited.add(start) # Marked as visited immediately
        while stack:
            node = stack.pop()
            for neighbor in adj_list[node]:
                if neighbor not in visited:
                    visited.add(neighbor) # Marked as visited before being pushed
                    stack.append(neighbor)

    counter = 0
    for node in range(n):
        if node not in visited:
            traverse(node)
            counter += 1

    return counter

# Tests
print(count_components(3, [[0,1], [0,2]]))   # 1
print(count_components(6, [[0,1], [1,2], [2,3], [4,5]]))  # 2
print(count_components(2, []))   # 2
print(count_components(0, []))   # 0

נסביר:

1. קודם יוצרים רשימת סמיכויות adjacency list לייצוג הגרף.
2. משתמשים בסט visited על מנת לעקוב אחרי הצמתים nodes בהם ביקרנו.
3. עבור כל צומת מריצים סריקת DFS (אלגוריתם חיפוש לעומק).
4. בכל פעם שסריקה מסתיימת מוסיפים 1 למונה.

פתרון רקורסיבי

def count_components(n, edges):
    adj_list = {i: [] for i in range(n)}
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)

    visited = set()

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for nei in adj_list[node]:
            dfs(nei)

    return sum(1 for node in range(n) if node not in visited and not dfs(node))

בעד ונגד פתרון רקורסיבי:

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

סיבוכיות

• סיבוכיות זמן: O(V + E)

  מבקרים כל צומת וכל קרן בדיוק פעם אחת.

• סיבוכיות מקום: O(V + E)

  • הגורם הדומיננטי הוא רשימת הסמיכויות הדורשת O(V) עבור איכלוס כל צומת, ובנוסף O(E) כיוון שכל edge נשמר פעמיים (דו־כיווני). סה״כ O(V+E).
  • הסט visited דורש O(V) מקום (במקרה שכל הצמתים יסרקו).
  • המחסנית (stack) עשויה להכיל עד O(V) צמתים במקרה הגרוע ביותר.
  • נסכם: O(V+E) + O(V) + O(V). מאחר ש־O(V+E) כבר כולל את רכיב O(V), הסיבוכיות הכוללת נותרת O(V+E).
  • לכן סה״כ: O(V + E).

  אם האלגברה של מציאת הסיבוכיות אינה ברורה אז ממליץ על קריאת המדריך big-O ביטוי ליעילות הקוד שם תקבל הסבר מפורט.

לסיכום

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

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

אלגוריתם חיפוש לעומק DFS - מהבנה ליישום

הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר

אתגר תכנותי : Graph Valid Tree

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים