java  
/*  
// Definition for a Node.  
class Node {  
    public int val;  
    public List<Node> neighbors;  
    public Node() {  
        val = 0;  
        neighbors = new ArrayList<Node>();  
    }  
    public Node(int _val) {  
        val = _val;  
        neighbors = new ArrayList<Node>();  
    }  
    public Node(int _val, ArrayList<Node> _neighbors) {  
        val = _val;  
        neighbors = _neighbors;  
    }  
}  
*/  
  
class Solution {  
    public Node cloneGraph(Node node) {  
         
        if (node == null) {  
            return node;  
        }  
  
        Set<Integer> visited = new HashSet<>();  
        Map<Integer, Node> clones = new HashMap<>();  
        Queue<Node> q = new LinkedList<>();  
        q.add(node);  
  
        while (!q.isEmpty()) {  
  
            Node currNode = q.poll();  
            int currVal = currNode.val;  
  
            if (!visited.contains(currVal)) {  
  
                Node nodeClone = clones.getOrDefault(currVal, new Node(currVal));  
                clones.put(currVal, nodeClone);  
  
                for (Node child : currNode.neighbors) {  
                    if (child == null) continue;  
                    Node childClone = clones.getOrDefault(child.val, new Node(child.val));  
                    clones.put(child.val, childClone);  
                    nodeClone.neighbors.add(childClone);  
                    q.add(child);  
                }  
                  
                visited.add(currVal);  
            }  
        }  
  
        return clones.isEmpty() ? node : clones.get(1);  
    }  
}