CloneGraphBFS.java

public Node cloneGraphBFS(Node node) {
    if (node == null) {
        return node;
    }

    Map<Node, Node> lookup = new HashMap<>();

    Queue<Node> q = new LinkedList<>();
    q.add(node);
    lookup.put(node, new Node(node.val, new ArrayList<>()));

    while (!q.isEmpty()) {
        Node cur = q.poll();

        for (Node n : cur.neighbors) {
            Node copiedNeighbor = null;

            if (!lookup.containsKey(n)) {
                // the neighbors would be populated later when it's popped out from the queue
                copiedNeighbor = new Node(n.val, new ArrayList<>());
                lookup.put(n, copiedNeighbor);
                q.add(n);
            } else {
                copiedNeighbor = lookup.get(n);
            }
            lookup.get(cur).neighbors.add(copiedNeighbor);
        }
    }
    return lookup.get(node);
}