Medium DFS + Map Advanced Graphs
In plain English: Make a complete copy of a graph where each node and its connections are duplicated.
Use a hashmap from original node to cloned node. DFS through the graph — if a neighbor is already cloned, reuse it; otherwise clone and recurse.
Prompt
Given a reference to a node in an undirected connected graph, return a deep copy of the graph. Each node has a value and a list of neighbors.
Try to write it from scratch before scrolling down.
Solution
class GraphNode:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def clone_graph(node):
if not node:
return None
cloned = {}
def dfs(n):
if n in cloned:
return cloned[n]
copy = GraphNode(n.val)
cloned[n] = copy # map original -> clone
for nb in n.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)
# Test: graph 1--2--3--1 => cloned graph with same structure