Clone Graph | Leetcode

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

OJ's undirected graph serialization:
 
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

---

Solution: A tricky breadth-first search (BFS) algorithm. The main trick is to add the node to the seen set as soon as you put it in the BFS queue. If you put it in the seen set after you pop the node from the queue, then you run a risk of having duplicates, which means you will not pass the Leetcode submission.

For each loop of the BFS, add all the neighbors to the BFS queue, but do not recurse into their neighbors yet.

Maintain a hashmap of all new nodes created so far so that we do not create the same node twice.

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        
        Set<Integer> seen = new HashSet<>();
        Map<Integer, UndirectedGraphNode> newNodes = new HashMap<>();
        LinkedList<UndirectedGraphNode> bfsQueue = new LinkedList<>();
        bfsQueue.addLast(node);
        seen.add(node.label);
        
        do {
            UndirectedGraphNode curNode = bfsQueue.removeFirst();
            UndirectedGraphNode newNode = getOrCreateCloneNode(newNodes, curNode.label);
            for (UndirectedGraphNode neighbor: curNode.neighbors) {
                newNode.neighbors.add(getOrCreateCloneNode(newNodes, neighbor.label));
                if (!seen.contains(neighbor.label)) {
                    bfsQueue.addLast(neighbor);
                    seen.add(neighbor.label);
                }
            }
        } while (!bfsQueue.isEmpty());
        
        return newNodes.get(node.label);
    }
    
    private UndirectedGraphNode getOrCreateCloneNode(
            Map<Integer, UndirectedGraphNode> newNodes, int label) {
        UndirectedGraphNode newNode = newNodes.get(label);
        if (newNode == null) {
            newNode = new UndirectedGraphNode(label);
            newNodes.put(label, newNode);
        }
        return newNode;
    }
}