Deep Copy A Graph
Problem
Given a reference to one node of a connected undirected graph, build an independent copy of the whole graph and return the matching node. Every node in the copy must be a new object, and the copy must have exactly the same connections as the original. The graph may contain cycles, and an absent reference copies to nothing.
Examples
Input: a square: 1 - 2 - 3 - 4 - 1
Output: a new square with the same four labels and the same four linksInput: the same square, comparing the copied node with the original
Output: they are different objects
Why: sharing even one node would make it a shallow copyInput: no node at all
Output: nothing
Why: edge case, there is no graph to copyHints
0 / 3
Walking the graph is the easy half. The hard half is that the same node is reached again from a different direction, and it must not be copied twice.
Keep a record that maps each original node to the copy you already made for it, and consult it before creating anything.
Visit from the given node. On arrival, return the existing copy if the record already has one. Otherwise create the copy and store it in the record before visiting any neighbour, so a cycle coming back around finds the copy instead of starting again.
Solution
A map from original node to its copy makes the traversal idempotent: arriving at a node a second time returns the copy already made instead of building another. The crucial ordering is that the copy is recorded before its neighbours are visited, because otherwise a cycle would come back to an unrecorded node and recurse forever. With that in place the neighbour lists are filled by the same routine applied to each neighbour. Each node and edge is handled once, so time is O(V + E) and space is O(V).
class G:
def __init__(self, val): self.val, self.nbrs = val, []
def clone(node, made=None):
if node is None:
return None
made = {} if made is None else made
if node in made:
return made[node] # this node was already copied
made[node] = copy = G(node.val) # record BEFORE recursing, so cycles stop
copy.nbrs = [clone(nb, made) for nb in node.nbrs]
return copy
def adjacency(node): # read a graph back as a plain map
out, stack, seen = {}, [node], {node}
while stack:
cur = stack.pop()
out[cur.val] = sorted(n.val for n in cur.nbrs)
for nb in cur.nbrs:
if nb not in seen: seen.add(nb); stack.append(nb)
return dict(sorted(out.items()))
a, b, c, d = G(1), G(2), G(3), G(4)
for x, y in ((a, b), (b, c), (c, d), (d, a)): x.nbrs.append(y); y.nbrs.append(x)
print(adjacency(clone(a))) # -> {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}
print(clone(a) is a) # -> False
print(clone(None)) # -> NoneStuck on the idea rather than the code? Depth-First Search covers it.