# 0133. Clone Graph
###### tags: `Leetcode` `FaceBook` `Medium` `Deep Copy` `DFS` `BFS`
Link: https://leetcode.com/problems/clone-graph/
深度拷贝问题的核心就是如何解决下一个要连的点还没被创建的问题
解决方法就是先创建新的再访问，为了避免重复创建，建一个map
## Code
DFS

class Solution {
    Map<Node,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
        Node newNode = new Node(node.val);
        map.put(node,newNode);
        newNode.neighbors = new ArrayList<Node>();
        for(Node neighbor:node.neighbors){
            if(map.containsKey(neighbor)){
                newNode.neighbors.add(map.get(neighbor));
            }
            else{
                newNode.neighbors.add(cloneGraph(neighbor));
            }
        }
        return newNode;
    }
}

BFS

class Solution {
    Map<Node,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
        Node newNode = new Node(node.val);
        Queue<Node> q = new LinkedList<>();
        map.put(node, newNode);
        q.add(node);
        while(!q.isEmpty()){
            Node curr = q.poll();
            for(Node neighbor:curr.neighbors){
                if(!map.containsKey(neighbor)){
                    map.put(neighbor, new Node(neighbor.val, new ArrayList<Node>()));
                    q.add(neighbor);
                }
                map.get(curr).neighbors.add(map.get(neighbor));
            }
        }
        return newNode;
    }
}