Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

• Time: O(n)
• Space: O(1)

public UndirectedGraphNode cloneGraphBFS(UndirectedGraphNode node) {
    if (node == null) return null;
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    queue.offer(node);
    map.put(node, new UndirectedGraphNode(node.label));
    while (!queue.isEmpty()) {
        UndirectedGraphNode n = queue.poll();
        for (UndirectedGraphNode a : n.neighbors) {
            if (!map.containsKey(a)) {
                map.put(a, new UndirectedGraphNode(a.label));
                queue.offer(a);
            }
            map.get(n).neighbors.add(map.get(a));
        }
    }
    return map.get(node);
}