# BFS Implementation in Python 3

def bfs(graph, root):
visited, queue = [], [root]
while queue:
vertex = queue.pop(0)
for w in graph[vertex]:
if w not in visited:
visited.append(w)
queue.append(w)

graph = {0: [1, 2], 1: [2], 2: []}
bfs(graph, 0)


Does this look like a correct implementation of BFS in Python 3?

• sets perform containing checks (w in visited) $O(1)$ rather than $O(n)$ for lists.
• collections.deque are better than lists for poping elements at the front (popleft).
• you should put your example code under an if __name__ == '__main__' clause.
• w as a variable name does not convey meaning, you should try to come up with something more explicit.
import collections

visited, queue = set(), collections.deque([root])
while queue:
vertex = queue.popleft()
for neighbour in graph[vertex]:
if neighbour not in visited:
queue.append(neighbour)

if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: []}

• But the code is poping elements from the right? – Christofer Ohlsson Aug 2 '18 at 14:44
• @ChristoferOhlsson Which code? OP uses list.pop(0) which pop from the left and mine uses deque.popleft() which, well, also pop from the left. – Mathias Ettinger Aug 2 '18 at 14:48
• I'm sorry, I must be blind. For some reason, I didn't realize OP used 0 as an argument. – Christofer Ohlsson Aug 2 '18 at 14:51
• You forgot to 'return visited' – AndyK Oct 2 '18 at 8:39
• I'm still grocking this, but it doesn't return anything right? – Scott Skiles May 17 at 2:07

I agree with Mathias Ettinger's use of sets and deques, with two changes:

• name the set seen instead of visited, because your algorithm adds to set before visiting.
• add the root to seen before entering while loop. Otherwise the root may be revisited (eg test case below where 1 points back to 0).

import collections

def bfs(graph, root):
seen, queue = set([root]), collections.deque([root])
while queue:
vertex = queue.popleft()
visit(vertex)
for node in graph[vertex]:
if node not in seen:
queue.append(node)

def visit(n):
print(n)

if __name__ == '__main__':
graph = {0: [1, 2], 1: [2, 0], 2: []}
bfs(graph, 0)


Outputs:

0
1
2


## protected by Jamal♦Oct 3 '18 at 1:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).