133. Clone Graph

Question: Clone Graph

Solution1

想法：

因為 node 是彼此的鄰居，如果從 node1 開始往右看，會看到 node2，做一個新的 node2 放到 node1 的 neighbors 裡，但做新的 node2 又要看到 node2 的 neighbors，有 node1 之外，還有 node3，所以又要做一個新的 node3。做新的 node3 要看 node3 的 neighbors，除了原本的 node2 之外還有 node4，所以要做新的 node4，node4 的 neighbors 有 node1 跟剛才新做的的 node3，可以發現又回到了最一開始已經做的 node1。

• 由上述可以發現，要一層一層 node 往下找 → DFS
• 最後又回到了需要最一開始新做的 node1，代表新做的 node 又會拿出來用，所以要存起來。
  • 每創造一個新的 node，例如創造 node2，要去找他的 neighbors: node1 跟 node3，其中 node3 是還要再新增的，但是 node1 是剛剛已經建立的，所以需要一個 data structure 把新建立的 node 存起來，如果建立過，就直接回去拿來用。這是需要 old_to_new hash map 的原因。
• 遞迴 dfs: 做一個 function 是可以輸入 old node 輸出 new node
  • 終止條件:
    • 已經建立的 new node，如果存在 hash map 裡，就直接透過 old node return new node
    • 所以這個 hash map 的 key 就會是 old node，value 就會是 new node
  • 遞迴條件:
    • new node 的值是 old_node.val: new_node = Node(old_node.val)
    • new node 放入 hash map 中: old_to_new[old_node] = new_node
    • 連結鄰居：
      • 把 old node 的每一個鄰居拿出來，丟入 dfs function，給他 old node 會 output new node。new_node_neighbor = dfs(old_node_neighbor)
      • 把 new_node_neighbor 放入 new_node 的 neighbors list 中: new_node.neighbors.append(new_node_neighbor)

# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        old_to_new = dict()
        def dfs(old_node):
            if old_node in old_to_new:
                return old_to_new[old_node]
            new_node = Node(old_node.val)
            old_to_new[old_node] = new_node
            for neighbor in old_node.neighbors:
                new_node.neighbors.append(dfs(neighbor))
            return new_node
        return dfs(node) if node else None

Solution2

import deepcopy

# Definition for a Node.
from copy import deepcopy
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        return deepcopy(node)

Video Solution