Clone a graph
Problem Statement
Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a value and a list of neighbors.
Example:
- Input: Graph with nodes
1 -- 2 -- 3 -- 4 -- 1and2 -- 4 - Output: A new graph with the same structure but entirely new node objects.
Noob-Friendly Explanation
Imagine you have a group of friends where each person knows some other people. You want to create an exact copy of this friend group — but with completely new people who have the same names and same friendships. No one in the copy should point to anyone in the original group.
The tricky part: if Alice knows Bob, and Bob knows Alice, you need to make sure "Copy-Alice" knows "Copy-Bob" and vice versa — without accidentally mixing up the originals and copies. We use a HashMap to remember "original person → their copy."
Approach 1: Brute Force (BFS)
Intuition
Use BFS to traverse the original graph. For each node we visit, create its clone. Use a HashMap to map original nodes to cloned nodes, so we don't create duplicates.
Algorithm
- Clone the starting node and put it in the HashMap.
- Add the starting node to a BFS queue.
- For each node in the queue, iterate through its neighbors.
- If a neighbor hasn't been cloned yet, clone it and add to the queue.
- Add the cloned neighbor to the current cloned node's neighbor list.
import java.util.*;
public class CloneGraphBFS {
static class Node {
public int val;
public List<Node> neighbors;
public Node(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
}
}
public static Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
// Clone the starting node
map.put(node, new Node(node.val));
queue.add(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Node neighbor : current.neighbors) {
// If neighbor not yet cloned, clone it
if (!map.containsKey(neighbor)) {
map.put(neighbor, new Node(neighbor.val));
queue.add(neighbor);
}
// Link the cloned current node to cloned neighbor
map.get(current).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
public static void main(String[] args) {
// Build: 1 -- 2, 1 -- 4, 2 -- 3, 3 -- 4
Node n1 = new Node(1), n2 = new Node(2), n3 = new Node(3), n4 = new Node(4);
n1.neighbors.addAll(Arrays.asList(n2, n4));
n2.neighbors.addAll(Arrays.asList(n1, n3));
n3.neighbors.addAll(Arrays.asList(n2, n4));
n4.neighbors.addAll(Arrays.asList(n3, n1));
Node clone = cloneGraph(n1);
System.out.println(clone.val); // 1
System.out.println(clone.neighbors.size()); // 2
System.out.println(clone != n1); // true (different objects)
}
}Complexity Analysis
- Time Complexity: O(V + E) — we visit every node and edge once.
- Space Complexity: O(V) — for the HashMap and queue.
Approach 2: Optimal (DFS — Recursive)
Intuition
Use DFS recursion with a HashMap. When we visit a node, clone it, store the mapping, then recursively clone each neighbor. If a neighbor is already in the map, just reuse the clone.
Algorithm
- If the node is null, return null.
- If the node is already in the map, return its clone.
- Create a clone of the current node and add to map.
- Recursively clone all neighbors and add them to the clone's neighbor list.
- Return the clone.
import java.util.*;
public class CloneGraphDFS {
static class Node {
public int val;
public List<Node> neighbors;
public Node(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
}
}
static Map<Node, Node> map = new HashMap<>();
public static Node cloneGraph(Node node) {
if (node == null) return null;
// If already cloned, return the clone
if (map.containsKey(node)) {
return map.get(node);
}
// Clone the current node
Node clone = new Node(node.val);
map.put(node, clone);
// Recursively clone all neighbors
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor));
}
return clone;
}
public static void main(String[] args) {
Node n1 = new Node(1), n2 = new Node(2), n3 = new Node(3), n4 = new Node(4);
n1.neighbors.addAll(Arrays.asList(n2, n4));
n2.neighbors.addAll(Arrays.asList(n1, n3));
n3.neighbors.addAll(Arrays.asList(n2, n4));
n4.neighbors.addAll(Arrays.asList(n3, n1));
map.clear();
Node clone = cloneGraph(n1);
System.out.println(clone.val); // 1
System.out.println(clone != n1); // true
}
}Complexity Analysis
- Time Complexity: O(V + E) — each node and edge is visited once.
- Space Complexity: O(V) — for the HashMap and recursion stack.