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

בעיות גרפים לעיתים קרובות מרגישות מופשטות עד שמצליחים לחבר אותן למשהו מוכר. "עץ" הוא אחד מאותם מונחים שנשמעים מוכרים, ואכן במדעי המחשב tree הוא מבנה נתונים מעניין ושימושי במיוחד. במדריך זה, נפתח את שריר החשיבה האלגוריתמית המוקדשים לפתרון בעיות גרפים מסוג עצים על ידי כך שנציג ונפתור את האתגר LeetCode 178 - Graph Valid Tree.

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

נתון גרף ובו n צמתים (nodes) מאונדקסים מ-0 ל n-1 ורשימה של קרנות (edges) שאינן מכוונות (כל קרן מחבר שני צמתים באופן דו-כיווני), ועליך לכתוב פונקציה הבודקת האם הגרף הנוצר הוא "עץ תקני".

• כל הקרנות הם ייחודיות. כיוון שהקרנות אינן מכוונות [0, 1] זהה ל- [1, 0] ולפיכך שניהם לא יופיעו יחדיו ברשימת הקרנות.

דברים שחשוב להבין או מה הופך גרף ל"עץ תקני"

כשאנחנו אומרים "עץ" בהקשר של גרף, אנחנו מתכוונים לדבר מאוד מסוים והוא שהמבנה חייב לעמוד בשני תנאים:

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

ב. הוא חייב להיות מחובר (connected)
כל צומת חייב להיות נגיש מכל צומת אחר. ולפיכך, אין איים מבודדים.

אלה שני עמודי התווך. אם אחד מהם שבור, אין לך עץ.

אז, הגישה שלנו פשוטה:

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

מקרי בוחן

להלן כמה מקרי בוחן שכדאי להיעזר בהם כשעובדים על הפתרון:

# Test cases
print(graph_valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]))  # True: looks like a clean star-shaped tree

print(graph_valid_tree(5, [[0,1],[0,2],[0,3]]))  # False: only 4 edges for 5 nodes, so it must be disconnected

print(graph_valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))  # False : there's a cycle: 1 → 2 → 3 → 1

print(graph_valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]))  # True : same valid tree structure again

print(graph_valid_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]))  # False : another cycle (1 → 2 → 3 → 1)

print(graph_valid_tree(1, []))  # True : a single node is a valid tree

print(graph_valid_tree(0, []))  # True : an empty graph is trivially a tree

print(graph_valid_tree(4, [[0,1],[1,2],[2,3],[3,0]]))  # False : it's a full cycle (square)

אולי תנסה לפתור לבד

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

פתרון אפשרי

from collections import deque

def graph_valid_tree(n, edges):
    if n < 0: 
        raise ValueError("Number of nodes can't be lower than 0")
    if n == 0: 
        return True
    if len(edges) != n - 1:
        return False  # A tree must have exactly n - 1 edges

    # Build adjacency list
    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()
    stack = deque([(0, -1)])  # Start DFS from node 0, with no parent

    while stack:
        curr, parent = stack.pop()
        if curr in visited:
            return False  # Cycle detected
        visited.add(curr)
        for neighbor in adj_list[curr]:
            if neighbor != parent:
                stack.append((neighbor, curr))

    return len(visited) == n  # Check full connectivity

נסביר:

• בדיקה מהירה len(edges) != n - 1 אם הגרף לא כולל בדיוק n-1 קרנות המחברות בין הצמתים אז זה אינו עץ.

• רשימת סמיכויות (adjacency list) היא אמצעי יעיל לאחסון מבנה הגרף.

• סריקת DFS איטרטיבית הכוללת:

  1. סט visited מאפשר לעקוב אחר הצמתים בהם ביקרנו.
  2. כל פריט בערימה stack יכיל מידע על אחד הצמתים ועל ההורה שלו.
  3. אתחול ערימה stack עם הצומת הראשון, 0, ועם ההורה שלו שלא קיים ועל כן נקרא לו -1.
  4. הלולאה תמשיך לרוץ עד לריקון ה-stack.
  5. אם ביקרנו כבר באחד הצמתים זו עדות לקיום הפנייה מעגלית מה שאומר שהגרף אינו עץ תקני.
  6. לפני שמוסיפים צומת ל-stack יש לוודא שזה אינו ההורה parent של הצומת הנוכחי.
  7. לפני שהפונקציה מחזירה בודקים שמספר הצמתים אותם סרקנו זהה למספר הקורסים שיש לקחת. אם זה לא המצב אז אי אפשר לקחת את כל הקורסים ולכן הפונקציה תחזיר False.

הערכת סיבוכיות

• כיוון שאנחנו מבקרים כל צומת ו-edge פעם אחת במהלך הסריקה סיבוכיות הזמן הינה O(V + E).
• בעוד הסט visited וה-stack יכולים לאחסן לכל היותר את כל הצמתים ולפיכך O(V), רשימת הסמיכויות מכילה את הצמתים וה-edges ביניהם ולפיכך סיבוכיות המקום היא O(V + E).

למה כדאי לך לדעת כיצד לפתור את האתגר

זו נראית אולי משימה תכנותית פשוטה אבל היא מלמדת המון, בין השאר:

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

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

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

סריקת DFS איטרטיבית

יישום עצים בינאריים בפייתון

אלגוריתם דייקסטרה

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

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

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