Course4all
Join us on telegram
Home/dsa/Graphs/Clone Graph

Clone Graph

Master this topic with zero to advance depth.

Clone Graph

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.

Visual Representation

1 -- 2 | | 4 -- 3 Clone: 1' -- 2' | | 4' -- 3'
Medium

Examples

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Node 1 is connected to 2 and 4. Node 2 is connected to 1 and 3, etc.

Approach 1

Level II: Intermediate (BFS + HashMap)

Intuition

BFS uses a queue to visit nodes level-by-level. By using a HashMap to store original -> clone, we can manage complexity and cycles. Every time we encounter a neighbor, if it's not in the map, we clone it and add to the queue.

Thought Process

  1. Use a HashMap to store originalNode -> clonedNode.
  2. Push the start node to a queue and create its clone.
  3. While the queue is not empty:
    • Pop curr. For each neighbor nbr:
      • If nbr is NOT in the map (unvisited):
        • Create its clone and add it to the map.
        • Push nbr to the queue.
      • Add the cloneMap.get(nbr) to the cloneMap.get(curr)'s neighbors list.
  4. Return the clone of the input node.

Pattern: BFS with Mapping

⏱ O(V + E) - Standard BFS traversal.💾 O(V) - For the queue and the mapping.

Detailed Dry Run

1 -- 2

MapQueueAction
{1:1'}[1]Init
{1:1', 2:2'}[2]Pop 1, clone 2, add 2' to 1' neighbors
{1:1', 2:2'}[]Pop 2, 1 is in map, add 1' to 2' neighbors
java
import java.util.*;

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        map.put(node, new Node(node.val));
        Queue<Node> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            Node curr = q.poll();
            for (Node nbr : curr.neighbors) {
                if (!map.containsKey(nbr)) {
                    map.put(nbr, new Node(nbr.val));
                    q.add(nbr);
                }
                map.get(curr).neighbors.add(map.get(nbr));
            }
        }
        return map.get(node);
    }
}
Approach 2

Level III: Optimal (DFS + HashMap)

Intuition

DFS is often more concise for graph cloning as it mimics the structure of the graph through the call stack. The HashMap acts as our "visited" set while also storing the deep copies.

Thought Process

  1. Use a HashMap to store originalNode -> clonedNode.
  2. In DFS function:
    • If the node is NULL, return NULL.
    • If the node is already in the map, return the existing clone.
    • Otherwise, create a new clone and add it to the map.
    • For each neighbor of the original node, recursively call DFS and add the result to the clone's neighbor list.
  3. Return the DFS call for the input node.

Pattern: DFS with Mapping

⏱ O(V + E) - Each node and edge is visited once.💾 O(V) - For the recursion stack and the mapping.

Detailed Dry Run

1 -> [2, 4]

MapCallAction
{}DFS(1)Create 1', Map {1:1'}, Call DFS(2)
{1:1'}DFS(2)Create 2', Map {1:1', 2:2'}, Call DFS(3)
.........
{1:1', 2:2', 3:3', 4:4'}DFS(4)Return 4' to 1' neighbors list
java
import java.util.*;

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node clone = new Node(node.val);
        visited.put(node, clone);

        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}
← Previous QuestionNumber of Islands
Next Question →Pacific Atlantic Water Flow