Clone Graph

clone graph

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
     HashMap<UndirectedGraphNode, UndirectedGraphNode> oldToNew;
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) {
            return null;
        }
        // write your code here
        oldToNew = new HashMap<>();
        HashSet<UndirectedGraphNode> visited = new HashSet<>();
        dfs(node, visited);
        bfs(node);
        bfs(oldToNew.get(node));
        return oldToNew.get(node);
    }
    
    private void bfs(UndirectedGraphNode node) {
        HashSet<UndirectedGraphNode> visited = new HashSet<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        while(!queue.isEmpty()) {
            UndirectedGraphNode current = queue.poll();
            if(!visited.contains(current)) {
                //System.out.println("current node is " + current.label);
                visited.add(current);
                for (UndirectedGraphNode n: current.neighbors){
                    queue.offer(n);
                }
            }
        }
    }
    
    private void dfs(UndirectedGraphNode node, HashSet<UndirectedGraphNode> visited) {
        if(visited.contains(node)) {
            return;
        } else {
            UndirectedGraphNode newNode;
            if(oldToNew.containsKey(node)) {
                newNode = oldToNew.get(node);
            } else {
                newNode = new UndirectedGraphNode(node.label);
                oldToNew.put(node, newNode);
            }
            for (UndirectedGraphNode child : node.neighbors) {
                if(!oldToNew.containsKey(child)) {
                    UndirectedGraphNode newChild = new UndirectedGraphNode(child.label);
                    newNode.neighbors.add(newChild);
                    //newChild.neighbors.add(newNode);
                    oldToNew.put(child, newChild);
                    dfs(child, visited);
                } else {

                    UndirectedGraphNode newChild = oldToNew.get(child);
                    //newChild.neighbors.add(newNode);
                    newNode.neighbors.add(newChild);
                }
            }
            visited.add(node);
            return;
        }
    }
}