Breadth First Search in Python

What is Breadth First Search in Python?

Breadth-first search (BFS) is an algorithm for traversing graphs or trees. Breath-first searches for trees and graphs are almost the same. The only difference is that the graph may contain cycles, so we may traverse to the same node again. To avoid processing the same node again, we use the boolean visited array, which will mark the visited vertices. BFS uses a queue data structure for finding the shortest path in a graph.

Breadth-First Search Python Algorithm

The breadth-first search algorithm uses a queue and a visited array. We use the queue to get the next vertex to start the search, and the visited array is used to mark all the nodes that have been visited, so when it appears again, we will perform BFS on that node.

The algorithm works as follows:

• Create a queue and insert any one vertex of the graph at the back of the queue.
• Initialize a visited array and mark that vertex as visited.
• Follow the below process till the queue becomes empty:
  • Remove a front vertex from the queue.
  • Get all the adjacent vertices of the removed vertex.
  • If the adjacent vertex has not been visited, mark it as visited and insert it at the back of the queue.

How Does the Breadth First Search Algorithm Work with an Example?

Let’s have a look at the algorithm with an example. Here we have an undirected graph of 5 vertices.

Initialize the queue.

Start from node A and mark it as visited.

Now, we can see that there are 3 neighbors of node A that are unvisited, so alphabetically we use node B and mark it as visited, and add it to the queue.

Next, the unvisited node is C, so mark it as visited and add it to the queue.

Now, the node D remains, so mark it as visited and add it to the queue.

Now, node A is left with no unvisited nodes, so start removing nodes from the queue. So node B pops from the queue, and since B has only one neighbor, i.e., A, and it has already been visited, we move forward and pop the next node from the queue.

Node C is removed from the queue. C has two neighbors: A and D. They have already been visited.

Now, only D remains in the queue, so pop it from the queue and mark all its neighbors visited. So D has 3 neighbors: A, C, and E. But only E is not visited, so mark E as visited and add E to the queue.

At last, pop E from the queue, and mark it as visited, since E has only one neighbor, i.e., D, but it has already been visited. So our queue will become empty.

Now, our queue becomes empty, so we have completed the breadth-first search traversal of the graph.

Implementation of Breadth First Search in Python

Code:

Output:

Breadth-First Search Python Complexity

The breadth-first search algorithm's time complexity is O(V+E), where V denotes the number of vertices and E denotes the number of edges.

The breadth-first search algorithm has O(V) space complexity.

Applications of Breadth-First Search

Breadth-first search is a simple graph traversal method that has a surprising range of applications. Some of the applications are discussed below:

• Crawlers in Search Engines Breadth-first search is the main algorithm used for indexing web pages. The BFS algorithm starts from the source page and follows all the links associated with it.
• Peer-to-Peer Networking Breadth-first search can be used to find all the neighboring nodes in a peer-to-peer network. For example, BitTorrent uses BFS for peer-to-peer communication.
• GPS Navigation Systems The best algorithm for determining the shortest path from one location to another is breadth-first search.
• Ford-Fulkerson Algorithm To find the maximum flow in a network, use the Ford-Fulkerson algorithm.
• Shortest Path & Minimum Spanning Tree for an unweighted graph: Breadth-first search is used to find the shortest path & minimum spanning tree for an unweighted graph.

Related Articles

1. Breadth First Search (BFS) Algorithm
2. Depth First Search (DFS) Algorithm