Two Python BFS solutions


  • 0
    G

    Solution 2 (A better solution)

    # Definition for a undirected graph node
    # class UndirectedGraphNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.neighbors = []
    
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        # 2:41
        def cloneGraph(self, node):
            if not node:
                return None
    
            newHead = UndirectedGraphNode(node.label)
            queue = collections.deque([(node, newHead)])
            map = {}
    
            while queue:
                cur, newCur = queue.popleft()
                if cur in map:
                    continue
    
                for child in cur.neighbors:
                    newChild = map.get(child, None) or UndirectedGraphNode(child.label)
                    newCur.neighbors.append(newChild)
                    queue.append((child, newChild))
    
                map[cur] = newCur
    
            return newHead
    

    Solution 1

    # Definition for a undirected graph node
    # class UndirectedGraphNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.neighbors = []
    
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        # 2:04
        def cloneGraph(self, node):
            if not node:
                return None
    
            newHead = UndirectedGraphNode(node.label)
            map = {node: newHead}
            queue = collections.deque([node])
            
            while queue:
                cur = queue.popleft()
                
                for neighbor in cur.neighbors:
                    if neighbor not in map:
                        newNeighbor = UndirectedGraphNode(neighbor.label)
                        map[cur].neighbors.append(newNeighbor)
                        queue.append(neighbor)
                        map[neighbor] = newNeighbor
                    else:
                        map[cur].neighbors.append(map[neighbor])
                
            return newHead

  • 0
    E

    I think you solution 2 is wrong. You didn't handle the case where there is a loop in graph, instead you always create new child node when searching!


  • 0
    G

    The new child node is for the cloned graph, the current node from the original graph is being hashed in the dict. So we will skip any previous nodes(loop) before cloning it into the node graph


  • 0
    E

    But the graph can have loop, right? Let me clarify a little bit more: how do you build a connection between a new created node and an already created node.


  • 0
    G

    I see what you are saying, good catch.

    This can be solved by a simple one line change:

    newChild = map.get(child, None) or UndirectedGraphNode(child.label)
    

    I already updated the post to reflect this change


Log in to reply
 

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