Undirected Graph

133 Copy an Undirected Graph

• Use HashMap to store old and new Node

• BFS

  public class Solution {
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       if (node == null) return null;
       Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
       map.put(node, new UndirectedGraphNode(node.label));
       LinkedList<UndirectedGraphNode> queue = new LinkedList<>();
       queue.add(node);
  
       while(!queue.isEmpty()){
           UndirectedGraphNode curNode = queue.poll();
           for (UndirectedGraphNode neighbor: curNode.neighbors){
               if (!map.containsKey(neighbor)){
                   queue.add(neighbor);
                   map.put(neighbor, new UndirectedGraphNode(neighbor.label));
               }
               map.get(curNode).neighbors.add(map.get(neighbor));
           }
       }
       return map.get(node);
   }
  }

• DFS

  /**
  * Definition for undirected graph.
  * class UndirectedGraphNode {
  *     int label;
  *     List<UndirectedGraphNode> neighbors;
  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
  * };
  */
  public class Solution {
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       if (node == null) return null;
       Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
       map.put(node, new UndirectedGraphNode(node.label));
       dfs(node, map);
       return map.get(node);
   }
  
   private void dfs(UndirectedGraphNode node, 
                                  Map<UndirectedGraphNode, UndirectedGraphNode> map){
       if (node == null) return;
  
       for (UndirectedGraphNode neighbor: node.neighbors){
           if (!map.containsKey(neighbor)){
               map.put(neighbor, new UndirectedGraphNode(neighbor.label));
               dfs(neighbor, map);
           }
           // add neighbors
           map.get(node).neighbors.add(map.get(neighbor));
       }
   }
  }