> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/graph/undirected.md).

# 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));
       }
   }
  }
  ```