אתגר תכנותי : איך לשבט גרף

Leetcode 133 - Clone graph

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

הגדרת הבעיה

נתונה הפניה (reference) לאחד הצמתים בגרף לא מכוון ומקושר (connected undirected). יש לבנות ולהחזיר עותק עמוק (deep copy) של הגרף.

לכל צומת בגרף יש ערך (val) ורשימה של שכנים (neighbors):

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = [] if not neighbors else neighbors

נקודת ההתחלה תהיה תמיד הצומת עם val = 1. עלינו להחזיר את ההעתק של אותו צומת הקשור לשכנים המשובטים, וחוזר חלילה — למעשה, שיבוט עמוק של כל הגרף.

מימוש הפתרון

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

להלן הפתרון המלא:

def clone_graph(node):
    if not node:
        return None

    old_new = {}  # Maps the original node to its clone

    def dfs(old_node):
        if old_node in old_new:
            return old_new[old_node]

        new_node = Node(old_node.val)
        old_new[old_node] = new_node

        for neighbor in old_node.neighbors:
            new_neighbor = dfs(neighbor)
            new_node.neighbors.append(new_neighbor)

        return new_node

    return dfs(node)

בדיקת הפתרון

כדי לבחון את הפתרון נבנה גרף קטן המכיל 4 צמתים:

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

node1.neighbors = [node2, node4]
node2.neighbors = [node1, node3]
node3.neighbors = [node2, node4]
node4.neighbors = [node1, node3]

cloned_graph = clone_graph(node1)

אם ננסה להדפיס את `cloned_graph`, נקבל משהו כזה:

__main__.Node object at 0x743fae7fffb0

כתובת האובייקט בזיכרון. לא ממש עוזר להבין אם השכפול הצליח... אז ניצור פונקציה שתציג את הגרף כרשימת סמיכויות (adjacency list):

def to_adjacency_list(start_node):
    adj = {}
    old_new = set()

    def dfs(node):
        if node in old_new:
            return
        old_new.add(node)
        adj[node.val] = [n.val for n in node.neighbors]
        for neighbor in node.neighbors:
            dfs(neighbor)

    dfs(start_node)
    return [adj[i] for i in range(1, len(adj) + 1)]

עכשיו נוכל להשוות בין הגרף המקורי לעותק:

print("Original:", to_adjacency_list(node1))
print("Cloned  :", to_adjacency_list(cloned_graph))
print("Graphs equal in structure? ", to_adjacency_list(node1) == to_adjacency_list(cloned_graph))
print("Different objects? " , node1 is not cloned_graph)

הערכת יעילות הפתרון

זמן ריצה: O(V + E)

• V – מספר הצמתים, E – מספר הקשתות.
• נבקר פעם אחת בכל צומת, ונעבור פעמיים על כל אחת מהקשתות המקשרות בין הצמתים.

זיכרון: O(V)

• המילון old_new שומר עותק לכל צומת.
• עומק הקריאה הרקורסיבית עלול להיות עד V במקרים קיצוניים דוגמת גרף לינארי.

נסכם

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

למרות שזה נשמע מפחיד הפתרון מבוסס ה- DFS ורקורסיה עובד ביעילות, וקל לקרוא ולהבין אותו.

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

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

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

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

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

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