Java BFS solution One Pass


  • 0
    R

    To clone a graph, we need the following 3 steps:

    1. Traverse all nodes in the graph;
    2. Clone all the nodes;
    3. Clone all the edges(neighbors).

    Here, we use BFS to traverse the nodes. Since the graph is undirected, we need to use HashMap/HashSet to record the nodes we have already visited. In order to clone the nodes, we use a HashMap to record the map from old Node to new Node. For each node we visited, we will get its neighbors to clone the edges.

    The three steps can be implemented in one pass. For each node we poll from the queue, we will add its neighbors to the queue. Here we have to check the if the node already existed in the queue. Meanwhile, if the node not existed in the queue, we also clone the new node. Then to every neighbor, we clone the neighbors to the new node.

    The following is my code:

     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            // find all the node HashSet queue 
            // clone each node hashmap 
            
            if(node == null) return null;
            HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
            Queue<UndirectedGraphNode> queue = new LinkedList<>();
            
            // bfs initialize
            UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);
            queue.offer(node);
            map.put(node, newHead);
            
            while(!queue.isEmpty()) {
                UndirectedGraphNode oldNode = queue.poll();
                UndirectedGraphNode newNode = map.get(oldNode);
                
                for(UndirectedGraphNode oldNeighbor:oldNode.neighbors) {
                    // clone node;
                    if(!map.containsKey(oldNeighbor)) {
                        queue.offer(oldNeighbor);
                        map.put(oldNeighbor, new UndirectedGraphNode(oldNeighbor.label));
                    }
                    UndirectedGraphNode newNeighbor = map.get(oldNeighbor);
                    // clone edge
                    newNode.neighbors.add(newNeighbor);
                }
            }
            
            return newHead;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.