# Python BFS solution using 2 queues for source and destination

• Simply perform BFS for a original graph, while using hashmap visited to avoid revisit the same node.
While performing BFS we use a queue to manage each level.
In the same manner, we create a queue for cloned graph and every time we pop the value from original queue, we put it back to destination queue.

class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if not node:
return None

visited = {} # store visited label
queue = [node] # queue for original BFS

res = UndirectedGraphNode(0) # start point of cloned graph
cloneQueue = [res] # queue for cloned graph BFS
while queue:
qlen = len(queue)
for i in range(qlen):
source = queue[0]
queue.pop(0)

destination = cloneQueue[0]
cloneQueue.pop(0)

destination.label = source.label # copy the label value from source to destination

for neighbor in source.neighbors:
destination.neighbors.append(UndirectedGraphNode(neighbor.label))

if neighbor.label not in visited:
visited[neighbor.label] = True

queue.append(neighbor)
cloneQueue.append(destination.neighbors[-1]) # push the cloned neighbor
return res

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