133. Clone Graph - Detailed Explanation

Problem Statement

You are given a reference to a node in a connected undirected graph. Each node in the graph contains a value and a list of its neighbors. The goal is to return a deep copy (or clone) of the graph. A deep copy means that you create new nodes and new edges that mirror the structure and connections of the original graph.

Graph Node Structure (for example):

• Node Structure:
  • val: An integer representing the node's value.
  • neighbors: A list (or array) of references to neighboring nodes.

Example:

Consider the graph represented as an adjacency list:

   1
  / \
 2---3
  \ /
   4

• Each node (1, 2, 3, 4) has a list of its neighbors.
• Your task is to produce a completely new graph that is identical in structure and values, but with all new node instances.

Hints for the Approach

• Hint 1:
  Think about how you can traverse the entire graph. Since the graph is connected, you can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to visit every node.

• Hint 2:
  To avoid revisiting and re-cloning nodes (which would lead to an infinite loop because of cycles), use a hash map (or dictionary) that maps original nodes to their cloned counterparts. This map will serve as a memoization tool so that if you encounter a node that has already been cloned, you can simply reuse the clone.

Approaches

There are two popular approaches to clone the graph:

Approach 1: DFS (Recursive)

Idea

1. Recursive Traversal:
   Start at the given node and use DFS to traverse the graph.
2. Clone on the Fly:
   For each node, create a clone and store it in a dictionary.
3. Clone Neighbors:
   Recursively clone each neighbor and add the clone to the neighbors list of the current node’s clone.
4. Memoization:
   Before cloning a node, check the dictionary. If it is already cloned, simply return the clone to avoid cycles and repeated work.

Pseudocode

function cloneGraph(node):
    if node is None:
        return None
    if node is in clonedMap:
        return clonedMap[node]
    clone = new Node(node.val)
    clonedMap[node] = clone
    for neighbor in node.neighbors:
        clone.neighbors.add(cloneGraph(neighbor))
    return clone

Approach 2: BFS (Iterative)

Idea

1. Iterative Traversal Using Queue:
   Use BFS to traverse the graph level by level.
2. Clone the Starting Node:
   Start by cloning the initial node and adding it to a queue.
3. Process the Queue:
   For each node taken from the queue, iterate through its neighbors.
   • If a neighbor is not yet cloned, clone it and add it to the queue.
   • Then, add the clone of the neighbor to the neighbors list of the current node’s clone.
4. Memoization:
   Use a dictionary (or map) to keep track of already cloned nodes.

Pseudocode

function cloneGraph(node):
    if node is None:
        return None
    clonedMap = new Map()
    queue = new Queue()
    clone = new Node(node.val)
    clonedMap[node] = clone
    queue.offer(node)
    while queue is not empty:
        current = queue.poll()
        for neighbor in current.neighbors:
            if neighbor is not in clonedMap:
                clonedMap[neighbor] = new Node(neighbor.val)
                queue.offer(neighbor)
            clonedMap[current].neighbors.add(clonedMap[neighbor])
    return clone

Detailed Step-by-Step Walkthrough

Let’s consider a small graph:

    1
   / \
  2   3
   \ /
    4

Using DFS:

1. Start at Node 1:
   • Create a clone for Node 1 and store it in the map.
2. Visit Neighbor Node 2:
   • Recursively clone Node 2 (not yet cloned, so create and store it).
   • For Node 2, process its neighbors.
3. Visit Neighbor Node 1 from Node 2:
   • Since Node 1 is already cloned (in the map), use the existing clone.
4. Visit Neighbor Node 4 from Node 2:
   • Clone Node 4 and add it.
5. Back to Node 1, process Neighbor Node 3:
   • Clone Node 3 and recursively process its neighbors.
6. Visit Neighbor Node 4 from Node 3:
   • Node 4 is already cloned; add the reference.
7. After processing all nodes, the DFS recursion unwinds, and every neighbor list in the cloned graph is filled accordingly.

Using BFS:

1. Initialize Queue with Node 1:

   • Clone Node 1 and add it to the map and the queue.

2. Process Node 1:

   • For each neighbor (Nodes 2 and 3), if not cloned, create clones, add them to the map and queue, and then link them.

3. Process Node 2:

   • For each neighbor (Node 1 and Node 4), check:
     • Node 1 is already cloned.
     • Clone Node 4 (if not already cloned) and add it to the queue.

4. Process Node 3:

   • For each neighbor (Node 1 and Node 4), add the references from the map.

5. Continue until the queue is empty, ensuring all nodes are processed.

Complexity Analysis

• Time Complexity:

  • Both DFS and BFS visit every node and every edge exactly once.

  • If V is the number of nodes and E is the number of edges, the time complexity is O(V + E).

• Space Complexity:

  • The dictionary (or map) stores a clone for each node: O(V).

  • The recursion stack (for DFS) or the queue (for BFS) in the worst-case also takes O(V).

  • Overall, O(V).

Python Implementation (Using DFS)