# Two Python BFS solutions

• Solution 2 (A better solution)

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

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

map = {}

while queue:
cur, newCur = queue.popleft()
if cur in map:
continue

for child in cur.neighbors:
newChild = map.get(child, None) or UndirectedGraphNode(child.label)
newCur.neighbors.append(newChild)
queue.append((child, newChild))

map[cur] = newCur

``````

Solution 1

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

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

queue = collections.deque([node])

while queue:
cur = queue.popleft()

for neighbor in cur.neighbors:
if neighbor not in map:
newNeighbor = UndirectedGraphNode(neighbor.label)
map[cur].neighbors.append(newNeighbor)
queue.append(neighbor)
map[neighbor] = newNeighbor
else:
map[cur].neighbors.append(map[neighbor])

• I think you solution 2 is wrong. You didn't handle the case where there is a loop in graph, instead you always create new child node when searching!

• The new child node is for the cloned graph, the current node from the original graph is being hashed in the dict. So we will skip any previous nodes(loop) before cloning it into the node graph

• But the graph can have loop, right? Let me clarify a little bit more: how do you build a connection between a new created node and an already created node.

• I see what you are saying, good catch.

This can be solved by a simple one line change:

``````newChild = map.get(child, None) or UndirectedGraphNode(child.label)
``````

I already updated the post to reflect this change

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