Clone a graph

Deep-copy a connected graph. A map from original node to its clone stops cycles from causing infinite recursion.

The idea

DFS (or BFS) from the start node, but before recursing into a neighbour check a map keyed by the original node. If the neighbour is already in the map, reuse its clone instead of recursing again; this is what keeps a cycle from looping forever.

Code

public static Node CloneGraph(Node start) {
    var map = new Dictionary<Node, Node>();
    return Clone(start, map);
}

static Node Clone(Node node, Dictionary<Node, Node> map) {
    if (map.TryGetValue(node, out var existing)) return existing;
    var copy = new Node(node.Val);
    map[node] = copy;
    foreach (var n in node.Neighbors)
        copy.Neighbors.Add(Clone(n, map));
    return copy;
}

Tips

• Populate the map entry for a node before recursing into its neighbours, in case one of them points back to it.
• The same idea works with BFS: queue a node only the first time it is added to the map.

In the .NET library

This is identical to the seen-set used in plain DFS, except the set is now a dictionary that also carries the payload (the clone) for each key.