← DSA Atlas
Dedicated problem page · #133

Clone Graph

MediumGraph DFS and BFSGraph traversal with clone mapBFS with a hash map from original to copy
Solve on LeetCode ↗
133
MediumGraph DFS and BFSBFS with a hash map from original to copyGraph traversal with clone map

Clone Graph

Given a reference to a node in a connected, undirected graph, return a deep copy (clone) of the entire graph. Each node holds an integer val and a list of its neighbors.

Open official problem prompt ↗
In plain English

Produce an independent copy of a graph whose shape matches the original exactly, including cycles.

Picture it like this

Like redrawing a subway map on fresh paper: each station gets drawn once, and every time a line points back to a station you already drew, you connect to that existing dot rather than drawing it again.

Example
Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]
Why
The clone is a brand-new set of 4 nodes with identical values and identical neighbor connections as the original.
Constraints
The number of nodes is in the range [0, 100]1 <= Node.val <= 100Node.val is unique for each nodeThere are no repeated edges and no self-loopsThe graph is connected and all nodes can be visited from the given node
Pattern lesson

See the pattern, then code

Graph traversal with clone map
Recognition clue

You must reproduce a graph's structure exactly while creating fresh objects; the challenge is handling cycles, which signals a visited/clone map.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Map each original node to its single clone the first time you see it; whenever an edge points to an already-cloned node, reuse that clone so shared references and cycles are preserved.

New words, made simpleKnow these before the algorithm
Deep copy
A new object graph that shares no node objects with the original.
Clone map
A dictionary from each original node to its unique copy, doubling as a visited set.
Undirected edge
A connection stored in both endpoints' neighbor lists.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Copy nodes then guess edges

Fragile and needs a value-to-clone map anyway; no real simplification.

Create nodes first, then try to reconnect by value.

Time O(V + E)Space O(V)
Best choiceBFS/DFS with clone map

Handles cycles cleanly and touches each node and edge once.

Clone each node on first visit, store it in a map, and mirror every edge using the map.

Time O(V + E)Space O(V)
The rule we keep true

Invariant

Every node placed in the clone map has exactly one corresponding copy, and any edge processed points from a clone to the already-existing clone of its neighbor.

Why this is correct

Reasoning

Because a node is cloned the first time it is discovered and never again, and every edge is mirrored through the map, the copy ends up isomorphic to the original with no duplicated or missing nodes.

The algorithm in three movesSay these aloud before coding
1Handle the empty input by returning None

clones = {1:1'}

2Create the clone of the start node and record it in a map

visit 1: create 2',4'; queue=[2',... ]

3BFS over originals; for each neighbor not yet cloned, create its clone and enqueue it

clones has all four; edges mirrored

4Wire clone-of-current to clone-of-neighbor for every edge

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
1 · Readnode = 1
2 · AskIs input null?
3 · Update stateclones={1:1'}, queue=[1]
4 · ResultClone of 1 created, enqueue original 1
Key takeaway

Four nodes in a square cycle; node 1 links to 2 and 4, which is copied edge-for-edge.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Null guard

    An empty graph clones to None.

  2. 2
    Lines 8-9Seed the map and queue

    Clone the start node up front so the map is never empty during traversal.

  3. 3
    Lines 11-17BFS and edge mirroring

    Clone unseen neighbors, enqueue them, and always append the neighbor's clone to the current clone's neighbor list.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • node is None (empty graph)
  • Single node with an empty neighbor list
  • A two-node graph forming a mutual edge
  • Dense cycles where every node points to every other
!

Common beginner mistakes

  • Cloning a neighbor again on a second visit, creating duplicate nodes
  • Adding the edge only when the neighbor is new, which misses edges to already-cloned nodes
  • Enqueuing the clone instead of the original node, breaking neighbor traversal
Check your understanding

Why is the edge wiring line placed outside the 'if nei not in clones' block?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill#339Nested List Weight SumDepth-weighted recursion over nested structure