Clone Graph
MediumGraphs
You get one node of a connected, undirected graph. Return a deep copy of the whole graph: new nodes with the same values and the same connections, sharing no node with the original.
Each node has a val and a list of neighbors. Values run from 1 to n, one per node. On this page a graph is written as an adjacency list: position i lists the neighbors of the node with value i + 1, and the node you get is the one with value 1.
Examples
Input: node = [[2, 3], [1, 3], [1, 2]] Output: [[2, 3], [1, 3], [1, 2]]
A triangle: each node links to the other two, and so must each copy.
Input: node = [[]] Output: [[]]
One node with no neighbors.
Constraints
- The graph has 0 to 100 nodes.
- Each value from 1 to n is used once.
- No edge repeats, and no node links to itself.
Stuck?
Hint 1
Keep a Map from each original node to its copy, so a node you reach twice is copied once.
Hint 2
Walk the graph with DFS or BFS. Make a node’s copy the first time you see it, then fill in its neighbors from the Map.
The idea
Copy the graph with a depth-first walk and a Map from each original node to its copy. The Map does two jobs: a node reached by more than one path gets one copy, and a walk that comes back around a cycle stops at a node it has already copied.
Time O(n + e) for n nodes and e edgesExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
An empty graph has nothing to copy. copies maps each original node to its copy, which is how a node reached twice still gets only one.
function cloneGraph(node) { if (!node) return null; const copies = new Map(); const copy = (original) => { if (copies.has(original)) return copies.get(original); const clone = new GraphNode(original.val); copies.set(original, clone); clone.neighbors = original.neighbors.map(copy); return clone; }; return copy(node);}The trap
This version makes a new node for the one it was given and hands it the original neighbour list. The values and the edges come out the same, which is why it looks right. But every node past the first is still an original, and their links lead back to the original first node, so any graph with more than one node shares nodes with the input.
function cloneGraph(node) { if (!node) return null; return new GraphNode(node.val, node.neighbors); // a new first node, but the old neighbors}