Clone Graph

BFS

Time Complexity

O(N)Space ComplexityO(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 nodeValue: 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
    
      map = new HashMap
     
      ();    Queue
      
        queue = new LinkedList
       
        ();    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 ComplexityO(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
    
      map = new HashMap
     
      ();    UndirectedGraphNode root = new UndirectedGraphNode(node.label);    map.put(node, root);    helper(node, map);    return root;}private void helper(UndirectedGraphNode node, Map
      
        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));    }}