Clone Graph

Creating deep copy of a connected graph.

https://leetcode.com/problems/clone-graph/

Solution 1: DFS

table = dict[Node, Node]()
 
def dfs(node: Optional['Node']) -> Optional['Node']:
    nonlocal table
    if not node or node in table:
        return
    clone = Node(node.val, [])
    table[node] = clone
    for neighbor in node.neighbors:
        clone.neighbors.append(
            table[neighbor] if neighbor in table else
            dfs(neighbor)
        )
    return clone
 
return dfs(node)

Solution 2: BFS

if not node:
    return
table = dict[Node, Node]()
root = node
queue = deque[Node]([root])
 
while queue:
    node = queue.popleft()
    if node in table:
        continue
    clone = Node(node.val, [])
    table[node] = clone
    for neighbor in node.neighbors:
        if neighbor in table:
            table[neighbor].neighbors.append(clone)
            clone.neighbors.append(table[neighbor])
        else:
            queue.append(neighbor)
 
return table[root]