leetcode133

 1 class Solution:
 2     def cloneGraph(self, node: 'Node') -> 'Node':
 3         if not node:
 4             return None
 5         queue = [node]
 6         dup_node = Node(node.val,[])
 7         fakequeue = [dup_node]
 8         visited = []
 9         d = {}
10         d[node.val] = dup_node
11         while queue:
12             node = queue.pop(0)
13             newnode = fakequeue.pop(0)
14             if node.val in visited:
15                 continue
16             visited.append(node.val)
17             for i in node.neighbors:
18                 if not i.val in d:
19                     j = Node(i.val,[])
20                     d[i.val] = j
21                 else:
22                     j = d[i.val]
23                 newnode.neighbors.append(j)
24                 queue.append(i)
25                 fakequeue.append(j)
26         return dup_node

算法思路：BFS

参考：https://leetcode.com/problems/clone-graph/discuss/440722/Python-3-BFS