Clone Graph LeetCode

• A queue is used to do breath first traversal.
• a map is used to store the visited nodes. It is the map between original node and copied node.

It would be helpful if you draw a diagram and visualize the problem.

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
         if(node == null)
            return null;

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
                                   new HashMap<UndirectedGraphNode,UndirectedGraphNode>();

        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        queue.add(node);
        map.put(node, newNode);
       
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.pop();
            List<UndirectedGraphNode> currNeighbors = curr.neighbors;
           
            for (UndirectedGraphNode ngn : currNeighbors) {
                if (!map.containsKey(ngn)) {
                    UndirectedGraphNode copy = new UndirectedGraphNode(ngn.label);
                    map.put(ngn, copy); //updating the mapping
                    map.get(curr).neighbors.add(copy); //updating the curr neighbors
                    queue.add(ngn); //updating the queue
                } else {
                    map.get(curr).neighbors.add(map.get(ngn)); //adding the node from clone graph to the curr's neighbor
                }
            }
        }
        return newNode;
    }