How do you clone a graph?

Q: How do you clone a graph?

**Target Audience:** Beginners preparing for coding interviews — you know Python classes, lists and dicts; graphs are explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First Imagine a group chat app that wants to let you **duplicate a friend group** so you can plan a surprise party without the guest of honour. Each person in the group is a card with a name and a list of "friends" — arrows pointing to other cards. Alice points to Bob, Bob points back to Alice and on to Carol, and so on. If you photocopy only Alice's card, the copy still points at the **real** Bob. Change "copy Bob" and you have actually changed the real Bob. That is a **shallow

The problem

Question presented to candidate: "You get a reference to one node of a connected, undirected graph. Each node has a value and a list of its neighbours. Return a deep copy of the whole graph — every node must be a new object, wired up the same way. Please write it in Python and tell me the complexity."

What a strong answer should cover:

A traversal (BFS with a queue or DFS with recursion) plus a dict mapping each original node → its copy; the map is both the visited set and the way to find the copy of a neighbour.
Why the map is mandatory: graphs have cycles, so copying without it loops forever (or duplicates nodes).
Inserting the copy into the map before visiting its neighbours, and handling the empty input (None).
O(V + E) time and O(V) extra space for the map and the queue (or the recursion stack).
Python specifics: collections.deque with popleft() for the queue (not list.pop(0)), node objects are hashable by identity unless the class defines __eq__ without __hash__, and recursive DFS hits the default recursion limit of 1000 on a long path.

Clarifying questions expected:

Is the input possibly None, and is everything reachable from the given node?
How big can the graph be (is recursion safe)?

Code / implementation expected: Yes — a clone_graph(node) function in Python using BFS or DFS with a dict, plus a check that the copy shares no node with the original.

graphs
hashing
bfs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python classes, lists and dicts; graphs are explained from scratch. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

Imagine a group chat app that wants to let you duplicate a friend group so you can plan a surprise party without the guest of honour. Each person in the group is a card with a name and a list of "friends" — arrows pointing to other cards. Alice points to Bob, Bob points back to Alice and on to Carol, and so on.

If you photocopy only Alice's card, the copy still points at

The solution is hidden so you can try first

15 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBFS clone with an old-to-new map: shape check and no shared nodes

Practice

PythonWhy the map matters: naive recursion vs DFS clone call counts, and BFS on a 10000-node path