Clone Graph

Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Tags: Graph

Try It!

Discussion

Video

Solution

"""
# 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':
        if not node:
            return None
        
        stack = []
        visited = {}
        stack.append(node)
        visited[node.val] = Node(node.val)

        while stack:
            top = stack.pop()

            for neighbor in top.neighbors:
                if neighbor.val not in visited:
                    stack.append(neighbor)
                    visited[neighbor.val] = Node(neighbor.val)
                visited[top.val].neighbors.append(visited[neighbor.val])
        return visited[node.val]        

DFS recursive solution

"""
# 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':
        if not node:
            return None
        
        visited = {}
        return self.dfs(node, visited)
    
    def dfs(self, node, visited):
        if node.val in visited:
            return visited[node.val]
        
        copy = Node(node.val)
        visited[node.val] = copy
        for nei in node.neighbors:
            copy.neighbors.append(self.dfs(nei, visited))
        return copy