Clone Graph

BFS

Time Complexity
O(N)
Space Complexity
O(N)

思路

Do a BFS traversal of the graph and while visiting a node make a clone node of it.

Use a hashmap to check if the node has already been created.
Key value: reference of original node
Value: reference of cloned node

How to connect clone nodes?
After all graph nodes has been made, get the corresponding cloned node u, then visit all the neighboring nodes of u and then connect the corresponding clone node then push it into queue.

代码

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    //coner case
    if(node == null) return null;
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    queue.offer(node);
    UndirectedGraphNode root = new UndirectedGraphNode(node.label);
    map.put(node, root);
    while(!queue.isEmpty()){
        UndirectedGraphNode cur = queue.poll();
        for(UndirectedGraphNode n : cur.neighbors){
            if(!map.containsKey(n)){
                map.put(n, new UndirectedGraphNode(n.label));
                queue.offer(n);
            }
            map.get(cur).neighbors.add(map.get(n));
        }
    }
    return root;
}

DFS

Time Complexity
O(N)
Space Complexity
O(N)

思路

You can think it as a tree, the level is how many nodes in the graph, each level represents all the neighbors of the nodes, after create all cloned nodes, then connect them together. Use the hashmap method as BFS method.

代码

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node == null) return node;
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
    UndirectedGraphNode root = new UndirectedGraphNode(node.label);
    map.put(node, root);
    helper(node, map);
    return root;
}

private void helper(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map){
    for(UndirectedGraphNode n : node.neighbors){
        if(!map.containsKey(n)){
            map.put(n, new UndirectedGraphNode(n.label));
            helper(n, map);
        }
        map.get(node).neighbors.add(map.get(n));
    }
}