Python BFS solution using 2 queues for source and destination


  • 0

    Simply perform BFS for a original graph, while using hashmap visited to avoid revisit the same node.
    While performing BFS we use a queue to manage each level.
    In the same manner, we create a queue for cloned graph and every time we pop the value from original queue, we put it back to destination queue.

    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if not node:
                return None
    
            visited = {} # store visited label
            queue = [node] # queue for original BFS
    
            res = UndirectedGraphNode(0) # start point of cloned graph
            cloneQueue = [res] # queue for cloned graph BFS
            while queue:
                qlen = len(queue)
                for i in range(qlen):
                    source = queue[0]
                    queue.pop(0)
    
                    destination = cloneQueue[0]
                    cloneQueue.pop(0)
    
                    destination.label = source.label # copy the label value from source to destination
    
                    for neighbor in source.neighbors:
                        destination.neighbors.append(UndirectedGraphNode(neighbor.label))
    
                        if neighbor.label not in visited:
                            visited[neighbor.label] = True
    
                            queue.append(neighbor) 
                            cloneQueue.append(destination.neighbors[-1]) # push the cloned neighbor
            return res
    

Log in to reply
 

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