Python Breadth-First Search Implementation

Breadth-First Search (BFS) is a fundamental algorithm for searching or traversing tree and graph data structures.

The algorithm works as below:

1. Select a node (the 'root' in a tree, or any node in a graph)
2. Visit all of the neighbor nodes at the current depth before moving on to nodes at the next depth level.

In rush? Go to the full code for the Python BFS implementation.

BFS is useful to find the shortest path of an unweighted graph.

In this tutorial, I will show you how to implement the BFS algorithm in Python the easy way. Keep reading!

How to Implement Breadth-First Search in Python

Follow the steps below to implement the BFS algorithm in Python.

1. Creating a Graph

Before we dive into the BFS algorithm, we need a graph to work with. I will use the graph as the one shown in the visualization above.

For simplicity, we'll use an adjacency list to represent a graph, where each node maps to a list of its neighbors.

graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F', 'G'],
  'D': [],
  'E': [],
  'F': [],
  'G': [],
}

2. Writing Breadth-First Search Algorithm in Python

The BFS algorithm pseudo code can be described as follows:

1. Start by putting any vertex at the back of a queue.
2. Take the front vertex of the queue, add it to the visited list.
3. For each vertex which is a neighbor of the front vertex and not visited, continue adding it to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

Common BFS implementation uses a queue to store the nodes to be visited. So I will use deque (pronounced as DECK) from the collections module to implement the queue for efficient pop and append operations.

Let's implement the BFS algorithm in Python.

from collections import deque

def bfs(graph, start):
  visited = set()  # Use a set to keep track of visited nodes for efficiency.
  queue = deque([start])  # Initialize a queue with the start node.

  while queue:
    vertex = queue.popleft()  # Pop a vertex off the queue.
    if vertex not in visited:
      visited.add(vertex)
      print(vertex, end=" ")  # Process the vertex (for example, print it out).

      # Skip if the vertex does not have any neighbors.
      if vertex not in graph:
        continue
      # Add neighbors of the vertex to the queue if they haven't been visited.
      for neighbor in graph[vertex]:
        if neighbor not in visited:
          queue.append(neighbor)

3. Testing the Python BFS Implementation

Let's test the bfs function with the graph we defined earlier. Here is the full code.

from collections import deque

def bfs(graph, start):
  visited = set()  # Use a set to keep track of visited nodes for efficiency.
  queue = deque([start])  # Initialize a queue with the start node.

  while queue:
    vertex = queue.popleft()  # Pop a vertex off the queue.
    if vertex not in visited:
      visited.add(vertex)
      print(vertex, end=" ")  # Process the vertex (for example, print it out).

      # Skip if the vertex does not have any neighbors.
      if vertex not in graph:
        continue
      # Add neighbors of the vertex to the queue if they haven't been visited.
      for neighbor in graph[vertex]:
        if neighbor not in visited:
          queue.append(neighbor)

graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F', 'G'],
  'D': [],
  'E': [],
  'F': [],
  'G': [],
}

# Assuming the graph is defined as shown in the previous section.
bfs(graph, 'A')  # Start the BFS traversal from node 'A'.

You can run this code by using the command: python bfs.py.

The output would be:

A B C D E F G

This output represents the order in which the nodes are visited when starting the BFS from node 'A'.

Conclusion

In this tutorial, we have learned how to implement the BFS algorithm in Python using a queue.

I know algorithm is hard to learn, but this is one of the most easiest algorithms. So read it again if you don't understand it the first time.