Problem. Each node of a connected undirected graph has a value and a list of neighbours. Given one node, return a deep copy of the whole graph: new node objects with the same values and the same connections, sharing nothing with the original.
1 — 2
| | clone(node 1) → a new graph 1' — 2', 1' — 4', 2' — 3', 3' — 4'
4 — 3
Copying a tree is easy (copy the node, recurse on the children). A graph has cycles and shared nodes (a node reachable along several paths), and copying must preserve both: the copy of a shared node must itself be shared, not duplicated.
ML context. Model objects are graphs: a decoder may tie its output embedding to the input embedding (one shared
module used twice), and modules hold references to each other. copy.deepcopy(model) must copy each shared object once and
keep it shared; that's exactly the memo map in this lesson (Change A). Copying the wrong way silently unties weights and
doubles memory.