How to implement a ​breadth-first search in Python

Key takeaways:

• Breadth-first search (BFS) is a graph traversal algorithm that explores all nodes at the current level before moving to the next.

• BFS can be implemented using a queue to manage the exploration order.

• It starts by inserting the starting node into the queue and marking it as visited.

• The algorithm continues by dequeuing nodes, visiting their unvisited neighbors, and adding them to the queue.

• The time complexity of BFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges.

• The space complexity of BFS is $O(V)$, where $V$ is the number of vertices.

Breadth-first search (BFS) is an algorithm used for traversing graphs or tree data structures. It explores all the vertices at the current level before moving to the next. BFS is commonly implemented using queues or linked lists to maintain the order of exploration.

The breadth-first search has a wide range of applications. For example, web crawlers can use BFS to build an index. It starts from a source page and follows links, ensuring comprehensive coverage. It can also help find people within a given distance from a person up to a specified level on social networking websites.

Algorithm

Let’s discuss the algorithm for the BFS:

1. Start: Insert the starting node into a queue. Mark the starting node as visited.

2. Explore: While the queue is not empty:

   1. Remove a node from the queue and print its value

   2. Insert all unvisited adjacent nodes of the removed node into the queue. Mark each adjacent node as visited to avoid revisiting.

3. End: Repeat the process until the queue is empty.

The following slides depict the flow of BFS in detail:

Code example

The following code example implements the BFS in Python:

Code explanation

• Lines 3–10: The illustrated graph is represented using an adjacency list. An easy way to do this in Python is to use a dictionary data structure, where each vertex has a stored list of its adjacent vertices or nodes.

• Line 12: The visited is a list that is used to keep track of visited nodes.

• Line 13: The queue is a list that is used to keep track of nodes currently in the queue.

• Line 29: The arguments of the bfs function are the visited list, the graph in the form of a dictionary, and the starting node A.

• Lines 15–26: The bfs follows the algorithm described above:

  • It checks and appends the starting node to the visited list and the queue.

  • Then, while the queue contains elements, it keeps taking nodes out of the queue, appends the neighbors of that node to the queue if they are unvisited, and marks them as visited.

  • This continues until the queue is empty.

Time complexity

Since all of ​the nodes are visited, the time complexity for BFS on a graph is $O(V + E)$; where $V$ is the number of vertices or nodes and $E$ is the number of edges.

Space complexity

The space complexity of BFS is $O(V)$, where $V$ represents the number of vertices or nodes in the graph.