133. Clone Graph

Loading...LeetCode

无向连通图的遍历，可以用BFS：

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return node
        
        visited = {} # a hashmap, where key = original node, value = new node copied from original one

        # Put the first node in the queue
        queue = collections.deque([node])
    
        # clone the starting node and put it in the visited dictionary.
        visited[node] = Node(node.val, [])
        while queue:
            target = queue.popleft()
            for neighbor in target.neighbors:
                # each round in BFS, we copy the neighbors of the nodes in queue
                # and avoid adding the visited nodes into queue
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited[neighbor] = Node(neighbor.val, [])
                # and the generated neighbor nodes into the neighbor list of target copy node
                visited[target].neighbors.append(visited[neighbor])
                
        return visited[node]

其实单纯这道题来说，DFS也没差，甚至更快点。把 popleft 改成 pop 就可以了（把queue变成了stack)