Sign in
Skip to solution
mediumDSA

How do you clone a graph?

257 views
01

Understand the problem

Explain deep-copying a graph.

graphshashingbfs
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Traverse with BFS or DFS, keeping a hash map from original node → its clone. When visiting an edge, create the neighbor's clone if unseen, then link clones. The map handles cycles and shared nodes. O(V+E).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

BFS with original→clone map
Run Playground
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

def clone_graph(node):
    if not node:
        return None
    clones = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                q.append(nb)
            clones[cur].neighbors.append(clones[nb])
    return clones[node]


# --- demo ---  square graph 1-2-3-4-1
a, b, c, d = Node(1), Node(2), Node(3), Node(4)
a.neighbors = [b, d]; b.neighbors = [a, c]
c.neighbors = [b, d]; d.neighbors = [a, c]
copy = clone_graph(a)
print(copy is not a)                              # True  (deep copy)
print(copy.val, [n.val for n in copy.neighbors])  # 1 [2, 4]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 85 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track