[Leetcode] Clone Graph

Problem

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Definition for undirected graph.

class UndirectedGraphNode {

      int label;

      List<UndirectedGraphNode> neighbors;

      UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); 

}};

       1

      / \

     /   \

    0 --- 2

           / \

           \_/

Algorithm

Use BFS or DFS to traverse the original graph. When exploring u's neighbors v, edge (u,v) may be a tree edge or back edge. 

• When (u,v) is a tree edge, we need to create a new node v_copy to the cloned graph, and add v_copy to u_copy's neighbors. 
• When (u,v) is a back edge, we need to find the reference of node v_copy, and add v_copy to u_copy's neighbors. 

In order to get the reference of a visited node in the cloned graph, we need a mapping from original node to copied node. A hash map with key = original node, and value = copied node can do this. Since each node only enters the BFS queue or DFS stack once, we will cover and copy each node and edge. The running time is simply O(n).  

Code