Python + BFS + deque + dictionary


  • 0

    BFS the Node, and by using a dictionary to store the processed or going to be processed nodes, which indicate they shouldn't be back to the queue, also can be referenced when need append to copy nodes neighbors.

    from collections import deque
    class Solution:
        def cloneGraph(self, node):
            if not node:
                return None
            copy = UndirectedGraphNode(node.label)
            dic = {node: copy}
            q = deque([ node ])
            while q:
                front = q.popleft()
                for nb in front.neighbors:
                    if not nb in dic:
                        dic[nb] = UndirectedGraphNode(nb.label)
                        q.append(nb)
                    dic[front].neighbors.append(dic[nb])
            return copy
    

Log in to reply
 

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