# Undirected Graph

## 133 Copy an Undirected Graph

* Use HashMap to store old and new Node
*   BFS

    ```java
    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

    ```java
    /**
    * 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));
         }
     }
    }
    ```
