Clone Graph
Problem
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph such that each node in the cloned graph has the same value and neighbors as the original graph.
- The number of nodes in the graph is in the range [0, 100]
- 1 ≤ Node.val ≤ 100
- Node.val is unique for each node
- The graph is connected and undirected
Example
node = [[2,4],[1,3],[2,4],[1,3]][[2,4],[1,3],[2,4],[1,3]]The input graph has 4 nodes with edges between 1-2, 1-4, 2-3, and 3-4. The algorithm starts cloning from node 1. It creates a copy of node 1, then recursively clones its neighbors 2 and 4. For neighbor 2, it clones node 2 and its neighbors 1 and 3. When it encounters node 1 again, it returns the already created copy to avoid infinite recursion. This process continues until all nodes are cloned, preserving the graph structure without duplication.
Approach
Straightforward Solution
A brute-force approach would attempt to clone nodes without tracking visited nodes, leading to infinite recursion or duplicated nodes. Another naive approach is to clone nodes iteratively but without memoization, which complicates neighbor linking and risks duplication.
Core Observation
Cloning a graph requires creating new nodes for each original node and replicating their neighbor relationships. Because graphs may contain cycles, naive recursion risks infinite loops unless visited nodes are tracked and reused.
Path to Optimal
The key insight is to use DFS with a hash map (memoization) that maps original nodes to their cloned counterparts. This map acts as a cache to prevent re-cloning nodes and to handle cycles gracefully. When a node is first encountered, a clone is created and stored in the map. Subsequent visits to the same node return the cached clone, ensuring each node is cloned exactly once and neighbor references are consistent.
Optimal Approach
Implement a recursive DFS function that, given a node, returns its clone. The function first checks if the node is already cloned in the map; if so, it returns the clone immediately. Otherwise, it creates a new node clone, stores it in the map, and recursively clones all neighbors, appending them to the clone's neighbors list. Finally, the function returns the clone. This approach guarantees a deep copy of the entire graph with O(N + E) time complexity.
Time
O(N + E)
Each node is visited once and each edge is explored once during the DFS traversal. The memoization map ensures no node is processed multiple times, resulting in linear time relative to the number of nodes and edges.
Space
O(N)
The recursion stack can grow up to O(N) in the worst case, and the memoization map stores a cloned node for each original node, both scaling linearly with the number of nodes.
Pattern Spotlight
DFS (Graph Cloning with Memoization)
When cloning graphs with cycles, use DFS combined with a map from original nodes to cloned nodes to avoid infinite recursion and ensure each node is cloned exactly once.
Solution
| 1 | # Definition for a Node.
|
| 2 | # class Node:
|
| 3 | # def __init__(self, val = 0, neighbors = None):
|
| 4 | # self.val = val
|
| 5 | # self.neighbors = neighbors if neighbors is not None else []
|
| 6 |
|
| 7 | class Solution:
|
| 8 | def cloneGraph(self, node: 'Node') -> 'Node':
|
| 9 | if not node:
|
| 10 | return None
|
| 11 |
|
| 12 | old_to_new = {}
|
| 13 |
|
| 14 | def dfs(node):
|
| 15 | if node in old_to_new:
|
| 16 | return old_to_new[node]
|
| 17 |
|
| 18 | copy = Node(node.val)
|
| 19 | old_to_new[node] = copy
|
| 20 | for neighbor in node.neighbors:
|
| 21 | copy.neighbors.append(dfs(neighbor))
|
| 22 | return copy
|
| 23 |
|
| 24 | return dfs(node) |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public Node cloneGraph(Node node) { |
| 5 | if (node == null) { |
| 6 | return null; |
| 7 | } |
| 8 | Map<Node, Node> oldToNew = new HashMap<>(); |
| 9 | |
| 10 | return dfs(node, oldToNew); |
| 11 | } |
| 12 | |
| 13 | private Node dfs(Node node, Map<Node, Node> oldToNew) { |
| 14 | if (oldToNew.containsKey(node)) { |
| 15 | return oldToNew.get(node); |
| 16 | } |
| 17 | |
| 18 | Node copy = new Node(node.val); |
| 19 | oldToNew.put(node, copy); |
| 20 | |
| 21 | for (Node neighbor : node.neighbors) { |
| 22 | copy.neighbors.add(dfs(neighbor, oldToNew)); |
| 23 | } |
| 24 | |
| 25 | return copy; |
| 26 | } |
| 27 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | Node* cloneGraph(Node* node) { |
| 9 | if (!node) { |
| 10 | return nullptr; |
| 11 | } |
| 12 | unordered_map<Node*, Node*> oldToNew; |
| 13 | return dfs(node, oldToNew); |
| 14 | } |
| 15 | |
| 16 | private: |
| 17 | Node* dfs(Node* node, unordered_map<Node*, Node*>& oldToNew) { |
| 18 | if (oldToNew.find(node) != oldToNew.end()) { |
| 19 | return oldToNew[node]; |
| 20 | } |
| 21 | |
| 22 | Node* copy = new Node(node->val); |
| 23 | oldToNew[node] = copy; |
| 24 | |
| 25 | for (Node* neighbor : node->neighbors) { |
| 26 | copy->neighbors.push_back(dfs(neighbor, oldToNew)); |
| 27 | } |
| 28 | |
| 29 | return copy; |
| 30 | } |
| 31 | }; |
| 1 | var cloneGraph = function(node) { |
| 2 | if (!node) { |
| 3 | return null; |
| 4 | } |
| 5 | const oldToNew = new Map(); |
| 6 | |
| 7 | function dfs(node) { |
| 8 | if (oldToNew.has(node)) { |
| 9 | return oldToNew.get(node); |
| 10 | } |
| 11 | |
| 12 | const copy = new Node(node.val); |
| 13 | oldToNew.set(node, copy); |
| 14 | |
| 15 | for (const neighbor of node.neighbors) { |
| 16 | copy.neighbors.push(dfs(neighbor)); |
| 17 | } |
| 18 | |
| 19 | return copy; |
| 20 | } |
| 21 | |
| 22 | return dfs(node); |
| 23 | }; |
Step-by-Step Solution
Handle Null Input to Return Empty Clone
| 9 | if not node:
|
| 10 | return None
|
Objective
To immediately return None if the input graph is empty, avoiding unnecessary processing.
Key Insight
An empty input graph means there is nothing to clone. Early returning None handles this edge case cleanly and prevents errors in the recursive cloning logic.
Interview Quick-Check
State & Boundaries
Check if the input node is None before starting DFS to handle empty graph edge case.
Initialize Memoization Map to Track Cloned Nodes
| 12 | old_to_new = {}
|
Objective
To create a dictionary that maps original nodes to their cloned counterparts, enabling cycle detection and reuse.
Key Insight
This map is the cornerstone of the cloning algorithm. It prevents infinite recursion by caching clones of nodes already processed. It also ensures that shared neighbors in the original graph are represented by shared clones in the copied graph, preserving structure.
Interview Quick-Check
Core Logic
The memoization map stores each original node's clone, enabling O(1) lookup to avoid re-cloning and handle cycles.
Common Pitfalls & Bugs
Failing to use a memoization map leads to infinite recursion on cyclic graphs or duplicated nodes.
Recursively Clone Nodes and Their Neighbors Using DFS
| 14 | def dfs(node):
|
| 15 | if node in old_to_new:
|
| 16 | return old_to_new[node]
|
| 18 | copy = Node(node.val)
|
| 19 | old_to_new[node] = copy
|
| 20 | for neighbor in node.neighbors:
|
| 21 | copy.neighbors.append(dfs(neighbor))
|
| 22 | return copy
|
Objective
To perform a depth-first traversal that clones each node and recursively clones all its neighbors, building the full deep copy.
Key Insight
The DFS function first checks if the node is already cloned to avoid duplication and infinite loops. If not cloned, it creates a new node clone and stores it in the map. Then it recursively clones each neighbor and appends the clones to the current node's neighbors list. This approach ensures that the entire graph is cloned correctly, including cycles and shared neighbors.
Interview Quick-Check
Core Logic
DFS uses the memoization map to return existing clones immediately, preventing infinite recursion and ensuring each node is cloned once.
State & Boundaries
The base case is when a node is already in the map, returning its clone without further recursion.
Common Pitfalls & Bugs
Appending neighbors after recursive calls ensures the cloned node's neighbors list correctly mirrors the original graph's structure.
Return the Cloned Graph Starting from Input Node
| 24 | return dfs(node) |
Objective
To initiate the cloning process by calling DFS on the input node and returning the fully cloned graph.
Key Insight
The initial call to DFS triggers the recursive cloning of the entire graph reachable from the input node. Returning the result of this call provides the deep copy of the original graph.
Interview Quick-Check
Core Logic
Starting DFS from the input node ensures the entire connected graph is cloned.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if node in old_to_new:Return the clone if the node has already been cloned.
This memoization check prevents infinite recursion by returning the existing clone immediately when a node is revisited.
old_to_new[node] = copyStore the clone in the map keyed by the original node.
Storing the clone before recursive neighbor cloning is critical to handle cycles and allow neighbor recursion to reference this clone.
old_to_new = {}Initialize a dictionary to map original nodes to their clones.
This map is essential to track cloned nodes, prevent infinite recursion on cycles, and ensure shared neighbors are cloned once and reused.
return old_to_new[node]Return the cached clone for the current node.
Returning the cached clone here ensures that the same node is never cloned multiple times, preserving graph structure and preventing cycles.
copy.neighbors.append(dfs(neighbor))Recursively clone each neighbor and append to the clone's neighbors list.
Appending the cloned neighbors builds the adjacency list of the cloned node, preserving the original graph's connectivity.
copy = Node(node.val)Create a new clone node with the same value as the original.
This line creates the deep copy of the current node, which will be linked to clones of its neighbors to form the cloned graph.
return copyReturn the fully constructed clone of the current node.
Returning the clone completes the recursion step, allowing parent calls to link to this cloned node.
return dfs(node)Start cloning by calling DFS on the input node and return the cloned graph.
This initiates the entire cloning process and returns the deep copy of the original graph to the caller.
if not node:Check if the input node is None (empty graph).
This early check prevents unnecessary processing and handles the edge case where the graph is empty, ensuring the function returns None immediately.
def dfs(node):Define the recursive DFS function to clone nodes.
Encapsulating the cloning logic in a recursive function allows systematic traversal and cloning of the graph, leveraging memoization to handle cycles.
for neighbor in node.neighbors:Iterate over each neighbor of the original node.
This loop explores all adjacent nodes to recursively clone the entire graph structure.
return NoneReturn None for empty input graph.
Returning None here correctly signals that there is no graph to clone, avoiding errors in subsequent logic.
Test Your Understanding
Why is it necessary to use a map from original nodes to cloned nodes during DFS cloning of a graph?
Because graphs can contain cycles and shared neighbors, the map prevents infinite recursion by returning already cloned nodes and ensures each node is cloned exactly once, preserving the graph structure correctly.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Clone Graph from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Clone Graph drill