DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Clone Graph

mediumGraphs

Problem statement

You get a reference to one node of a connected, undirected graph. Each node has an integer val (unique, from 1 to n) and a list neighbors of the nodes it links to.

Return a deep copy of the whole graph: brand-new node objects with the same values and the same links between them. No node in your copy may be an original node. If the input is null, return null.

Examples describe the graph as an adjacency list, where entry i lists the neighbours of the node with value i + 1, and the given node is the one with value 1.

Examples

Example 1

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

Output: [[2, 3], [1, 3], [1, 2]]

Explanation: A triangle. The copy has three new nodes linked the same way.

Example 2

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

Output: [[2], [1, 3], [2]]

Explanation: A path 1 - 2 - 3. Node 2's copy must link to the copies of 1 and 3, not to the originals.

Hints

Approach

One traversal, creating copies on first sight and wiring links as you go.

  1. Create the copy of the start node, store it in copies, and queue the original.
  2. Pop an original. For each neighbour: if it has no copy yet, create one, store it and queue the neighbour. Then append the neighbour's copy to the current node's copy.
  3. Return the copy of the start node.

The copies map is both the visited set and the lookup table. Because a copy is created the moment a node is first seen, a cycle back to it finds the existing copy instead of making a duplicate. Each node is queued once and each link is appended once from each side.

ComplexityTime O(V + E)Space O(V)
Python
from collections import deque
class Solution:
def cloneGraph(self, node: "Node | None") -> "Node | None":
if node is None:
return None
copies = {node: Node(node.val)}
queue = deque([node])
while queue:
cur = queue.popleft()
for nb in cur.neighbors:
if nb not in copies:
copies[nb] = Node(nb.val) # copy on first sight
queue.append(nb)
copies[cur].neighbors.append(copies[nb])
return copies[node]

Follow-up questions

  • The graph may be disconnected and you are given a list of all nodes. How do you copy all of it?
  • Clone a directed graph where edges carry a weight.

Frequently asked questions

Here values are unique, so it happens to work. Keying by the node object is the general answer, because it still works when two different nodes share a value.

Copying a structure with shared references and cycles comes up whenever you duplicate a stateful object graph: forking a service topology to build a staging copy, snapshotting a dependency graph before mutating it, or cloning a config tree whose sections reference each other. Getting a shallow copy by mistake means edits to the "copy" silently change production.

Yes, and it is shorter: create the copy, store it, then recurse into each neighbour. For graphs with long chains it can exceed Python's recursion limit, which is why the iterative version is shown.