Deep-copy a strategy dependency graph

Question

You have a directed graph of strategy nodes, each holding a value and a list of neighbor references. Produce a completely independent deep copy: same structure and values, but all-new node objects. The graph may contain cycles.

A -> B, B -> C, C -> A      # a 3-cycle
clone -> new A' -> B' -> C' -> A'  (no object shared with the original)

Return the clone of the given start node (the copy of the whole reachable graph).

Accepted Answer

DFS from the start node, keeping a map from each original node to its freshly created copy. Before recursing into a neighbor, check the map: if the copy already exists, reuse it, this both avoids infinite loops on cycles and preserves shared references. Create the copy and register it in the map before recursing into neighbors. Tracing the 3-cycle A - B - C - A: cloning A registers A', recurses to make B' and C', and when C' recurses back to A, the map already holds A', closing the cycle without infinite recursion. Time O(V + E), space O(V) for the map and recursion. Edge cases: a null start …

Deep-copy a strategy dependency graph

Your answer

More Coding questions