Clone Graph medium

Problem Statement

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

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. Node 1 has neighbors 2 and 4. Node 2 has neighbors 1 and 3. Node 3 has neighbors 2 and 4. Node 4 has neighbors 1 and 3.

Example 2

Input: adjList = [[]] Output: [[]] Explanation: The graph is empty.

Steps

  1. Handle Base Case: If the input graph is empty (node is None), return None.

  2. Create a Visited Dictionary: This dictionary will store the mapping between original nodes and their cloned copies. This prevents infinite recursion in case of cycles in the graph.

  3. Recursive Cloning: Define a recursive function cloneGraph that takes a node as input.

  4. Check if Node Visited: If the node is already in the visited dictionary, return its cloned copy.

  5. Create Cloned Node: Create a new node with the same value as the input node. Add it to the visited dictionary.

  6. Recursively Clone Neighbors: Iterate through the neighbors of the input node. For each neighbor, recursively call cloneGraph to get its cloned copy. Add the cloned neighbor to the cloned node's neighbor list.

  7. Return Cloned Node: Return the newly created cloned node.

  8. Initial Call: Call the cloneGraph function with the root node of the graph.

Explanation

The core idea is to use Depth-First Search (DFS) and a visited dictionary to avoid infinite loops and create a true deep copy. The visited dictionary is crucial because it ensures that each node is cloned only once. When a node is encountered for the second time (due to a cycle), its already-cloned counterpart is retrieved from the dictionary instead of being cloned again. This prevents the creation of multiple copies of the same node, leading to a correct deep copy of the graph.

Code

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

def cloneGraph(node):
    visited = {}  # Dictionary to store cloned nodes

    def dfs(node):
        if node is None:
            return None

        if node in visited:
            return visited[node]

        clone = Node(node.val)
        visited[node] = clone  # Mark the cloned node

        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

# Example usage (adapt to your input method):
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 = cloneGraph(node1)

#Verification (Optional, adapt to your printing needs)
print(f"Original graph: Node 1 neighbors: {[n.val for n in node1.neighbors]}")
print(f"Cloned graph: Node 1 neighbors: {[n.val for n in cloned_graph.neighbors]}")

Complexity

  • Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit each node and each edge exactly once.

  • Space Complexity: O(V), where V is the number of vertices. This is because the visited dictionary stores at most one entry for each node in the graph. The recursive call stack could also use O(V) space in the worst-case scenario (a very deep graph).