CodeEasy v0.1

Clone Graph

Medium Subject: Graphs
Time Complexity
O(V + E)
Space Complexity
O(V)

Problem Description

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a val and a list of its neighbors.

Optimal Solution

Python 
def cloneGraph(node):
    if not node:
        return None
    visited = {}

    def dfs(node):
        if node in visited:
            return visited[node]
        clone = Node(node.val, [])
        visited[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone

    return dfs(node)