Copy Graph
MediumMap original nodes to their clones
Problem
Return a deep copy (clone) of a connected undirected graph.
DFS/BFS the graph, making a fresh copy of each node the first time you see it and wiring up copies.
The idea
Keep a map from each original node to its copy and consult it before creating anything. That map is both the memo that stops infinite recursion on cycles and the way shared neighbours end up pointing at the same clone.
The trick
- Create the clone and record it in the map before recursing into neighbours.
- Without the map, a cycle recurses forever.
- O(V + E).
Step 1 of 11. DFS clone: on first visit, copy the node into a map, then recurse into neighbours.
One clone per original.
1function clone(node) {2 if (map.has(node)) return map.get(node);3 const copy = new Node(node.val);4 map.set(node, copy);5 for (const nb of node.neighbors)6 copy.neighbors.push(clone(nb));7 return copy;8}Input
- nodes
- 4, 4 edges
Memory
- cloned
- —
Output
- nodes
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- adjacency = [[2,4],[1,3],[2,4],[1,3]]
- Output:
- [[2,4],[1,3],[2,4],[1,3]]
- Explanation:
- A deep copy has the same shape and connections.
Example 2
- Input:
- adjacency = [[]]
- Output:
- [[]]
- Explanation:
- A single node with no neighbours.
Example 3
- Input:
- adjacency = []
- Output:
- []
- Explanation:
- Empty graph clones to empty.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.