# 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: []}


Given a growing number of comments indicating that the code does not return anything, I’d like to add that, yes, this code does not process nodes: it only traverse the graph and you're likely to want to add your own custom logic to process each node. As your mileage may vary (building a traversal list, finding the first node that satisfies a condition, etc.), there is not a "one code fits all" approach, but a useful first approximation would be to yield each node as they are traversed:

import collections

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

if __name__ == '__main__':
graph = {1: [2, 4, 5], 2: [3, 6, 7], 3: [], 4: [], 5: [], 6: [], 7: []}
list(breadth_first_search(graph, 1))  # [1, 2, 4, 5, 3, 6, 7]


Note that this alternative iteration also takes care of the bug mentioned in this answer

• But the code is poping elements from the right? Commented Aug 2, 2018 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. Commented Aug 2, 2018 at 14:48
• I'm sorry, I must be blind. For some reason, I didn't realize OP used 0 as an argument. Commented Aug 2, 2018 at 14:51
• You forgot to 'return visited' Commented Oct 2, 2018 at 8:39
• I'm still grocking this, but it doesn't return anything right? Commented May 17, 2019 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


The idea is to explore the vertex completely before moving onto the next vertex. For the below adjacency matrix:

test_graph = {
1: [2, 4, 5],
2: [3, 6, 7],
3: [],
4: [],
5: [],
6: [],
7: []
}


The output should be 1, 2, 4, 5, 7, 6, 3, or 1, 5, 4, 2, 3, 6, 7, etc. The idea is that the current vertex should be completely explored before moving onto the next vertex. In addition, connected vertices can occur in any order.

Below code provides the correct sequence

import collections

def bfs(graph, start_vertex):
visited = set()
traversal = []
queue = collections.deque([start_vertex])
while queue:
vertex = queue.popleft()
if vertex not in visited:
traversal.append(vertex)
queue.extend(reversed(graph[vertex]))   # add vertex in the same order as visited
return traversal