Python BFS iterative solution


  • 0
    G

    Detailed explanation below...
    Note the separate tracking of cloned and queued. Where it's possible to avoid the extra set the performance is better this because we completely avoid queueing already cloned/queued nodes.

    # Definition for a undirected graph node
    # class UndirectedGraphNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.neighbors = []
    
    from collections import deque
    
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if node is None: return None
            
            root = node.label
            cloned = {}  # all cloned nodes are stored here
            queued = {root}  # track queued nodes - see comment below regarding why
            q = deque()  # used for traversing; a node in the queue potentially wasn't cloned yet
            q.append(node)
    
            while len(q) > 0:
                node = q.popleft()
                lbl = node.label
                if lbl in cloned:
                    # already cloned
                    continue
                
                # actually clone the node
                new_node = UndirectedGraphNode(lbl)
                cloned[lbl] = new_node
                # copy neighbors as-is. later we'll replace with cloned nodes
                new_node.neighbors = node.neighbors
    
                # go over the neighbors and queue them up, if needed (there are more compact
                # ways of doing it, like simply extending the queue, but tracking queued nodes
                # will actually produce better performing results)
                for n in node.neighbors:
                    lbl = n.label
                    if lbl not in queued:
                        q.append(n)
                        queued.add(lbl)
            
            # iterate over all cloned nodes and replace the neighbors with cloned ones
            for node in cloned.itervalues():
                node.neighbors = [cloned[n.label] for n in node.neighbors]
                
            return cloned[root]
    

Log in to reply
 

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