BFS Implementation in Python 3

Question

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?

Answer 1

• 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


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


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

---

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


def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        yield vertex
        visited.add(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

Answer 2

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:
                  seen.add(node)
                  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
  

Answer 3

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:
            visited.add(vertex)
            traversal.append(vertex)
            queue.extend(reversed(graph[vertex]))   # add vertex in the same order as visited
    return traversal