5.2 Deep Copy Undirected Graph

Make a deep copy of an undirected graph, there could be cycles in the original graph.

Assumption: the given graph is not null

Input: List<GraphNode> graph

Output: List<GraphNode> a deep copy of the graph

Solution:

1. Build one-on-one relation b/w original node and it's copy to avoid being copied multiple times

2. Copy input node and the nodes reachable from it first

3. Use map <key: input node, value: copied node>, check if value exists.

class GraphNode {
  public int key;
  public List<GraphNode> neighbors;
  public GraphNode(int key) {
    this.key = key;
    this.neighbors = new ArrayList<GraphNode>();
  }
}

public List<GraphNode> copy(List<GraphNode> graph) {
  if (graph == null) {
    return null;
  }
  HashMap<GraphNode, GraphNode> map = new HashMap<>();
  for (GraphNode node : graph) {
    if (!map.containsKey(node)) {
      map.put(node, new GraphNode(node.key));
      dfs(node, map);
    }
  }
  return new ArrayList<GraphNode>map.values());
}

private void dfs(GraphNode node, HashMap<GraphNode, GraphNode> map) {
  GraphNode copy = map.get(node);
  for (GraphNode nei : node.neighbors) {
    if (!map.containsKey(nei)) {
      map.put(nei, new GraphNode(nei.key));
      dfs(nei, map);
    }
    //connect the copied neighbors to the copied node
    copy.neighbors.add(map.get(nei));
  }
}