# Python BFS iterative solution

• Detailed explanation below...
Note the separate tracking of cloned and queued. Where it's possible to avoid the extra `set` the performance is better this because we completely avoid queueing already cloned/queued nodes.

``````# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

from collections import deque

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

root = node.label
cloned = {}  # all cloned nodes are stored here
queued = {root}  # track queued nodes - see comment below regarding why
q = deque()  # used for traversing; a node in the queue potentially wasn't cloned yet
q.append(node)

while len(q) > 0:
node = q.popleft()
lbl = node.label
if lbl in cloned:
continue

# actually clone the node
new_node = UndirectedGraphNode(lbl)
cloned[lbl] = new_node
# copy neighbors as-is. later we'll replace with cloned nodes
new_node.neighbors = node.neighbors

# go over the neighbors and queue them up, if needed (there are more compact
# ways of doing it, like simply extending the queue, but tracking queued nodes
# will actually produce better performing results)
for n in node.neighbors:
lbl = n.label
if lbl not in queued:
q.append(n)