133. Clone Graph

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 (int) and a list (List[Node]) of its neighbors.

Examples

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.
1st node (val=1)'s neighbors are 2nd node (val=2) and 4th node (val=4).
2nd node (val=2)'s neighbors are 1st node (val=1) and 3rd node (val=3).
3rd node (val=3)'s neighbors are 2nd node (val=2) and 4th node (val=4).
4th node (val=4)'s neighbors are 1st node (val=1) and 3rd node (val=3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val=1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not contain any nodes.

Constraints

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The graph is connected and undirected.

Solution Approach

This problem requires creating a deep copy of a graph, meaning we need to create new nodes with the same structure and relationships as the original graph.

Key Insights:

  1. Deep copy: Create new nodes, not just copy references
  2. Graph traversal: Need to visit all nodes and their neighbors
  3. Avoid cycles: Use visited tracking to prevent infinite loops
  4. Node mapping: Map original nodes to cloned nodes
  5. Two approaches: BFS (iterative) or DFS (recursive)

Algorithm:

  1. Create node mapping: unordered_map<Node*, Node*> to track cloned nodes
  2. Traverse graph: Visit all nodes using BFS or DFS
  3. Clone nodes: Create new nodes with same values
  4. Build relationships: Connect cloned nodes based on original relationships
  5. Return root: Return the cloned version of the starting node

Solution

Solution 1: BFS (Iterative)

/*
// Definition for a Node.
class Node {

    # val = 0
    # neighbors = []
    # def __init__(self, val=0, neighbors=None):
    #     self.val = val
    #     self.neighbors = neighbors if neighbors is not None else []
*/

from collections import deque

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        visited = {}
        q = deque([node])
        visited[node] = Node(node.val)
        while q:
            curr = q.popleft()
            for neighbor in curr.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    q.append(neighbor)
                visited[curr].neighbors.append(visited[neighbor])
        return visited[node]

Solution 2: DFS (Recursive)

class Solution:
    def dfs(self, node: 'Node', visited: dict) -> 'Node':
        if node in visited:
            return visited[node]
        
        clone = Node(node.val)
        visited[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(self.dfs(neighbor, visited))
        return clone
    
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None
        visited = {}
        return self.dfs(node, visited)

Algorithm Explanation:

BFS Approach:

  1. Initialize: Create visited map and queue
  2. Start: Add original node to queue and create its clone
  3. Process: For each node in queue:
    • Create clones for unvisited neighbors
    • Add neighbors to queue for processing
    • Connect cloned nodes to their cloned neighbors
  4. Return: Return cloned version of starting node

DFS Approach:

  1. Base case: If node already cloned, return cloned version
  2. Create clone: Make new node with same value
  3. Recursive: For each neighbor, recursively clone and connect
  4. Return: Return the cloned node

Example Walkthrough:

For graph with nodes 1, 2, 3, 4:

Original Graph:
    1
   / \
  2---3
   \ /
    4

BFS Process:
1. Start with node 1, create clone(1)
2. Process node 1: create clone(2), clone(4), connect clone(1) to them
3. Process node 2: create clone(3), connect clone(2) to clone(1), clone(3)
4. Process node 4: connect clone(4) to clone(1), clone(3)
5. Process node 3: connect clone(3) to clone(2), clone(4)

Final cloned graph has same structure as original.

Complexity Analysis

Time Complexity: O(V + E)

  • V: Number of vertices (nodes)
  • E: Number of edges (neighbor relationships)
  • Traversal: Visit each node and edge exactly once
  • Cloning: O(1) per node creation

Space Complexity: O(V)

  • Visited map: O(V) - stores mapping from original to cloned nodes
  • Queue (BFS): O(V) - maximum nodes in queue
  • Recursion stack (DFS): O(V) - maximum recursion depth
  • Cloned graph: O(V + E) - not counted in auxiliary space

Key Points

  1. Deep copy: Create new nodes, not copy references
  2. Cycle handling: Use visited map to prevent infinite loops
  3. Node mapping: Track original → cloned node relationships
  4. Graph traversal: BFS or DFS both work effectively
  5. Edge cases: Handle null input and single node graphs

Comparison: BFS vs DFS

Aspect BFS DFS
Approach Iterative Recursive
Space Queue + Map Recursion Stack + Map
Code More verbose More concise
Stack overflow No risk Risk with deep graphs
Performance Similar Similar

Alternative Approaches

DFS Iterative (Stack)

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        visited = {}
        stk = [node]
        visited[node] = Node(node.val)
        
        while stk:
            curr = stk.pop()
            
            for neighbor in curr.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    stk.append(neighbor)
                visited[curr].neighbors.append(visited[neighbor])
        
        return visited[node]

Tags

Graph, DFS, BFS, Clone, Deep Copy, Medium