Breadth First Search (BFS) Algorithm with EXAMPLE

Details

What is BFS Algorithm (Breadth-First Search)?

Breadth-first search (BFS) is an algorithm that is used to graph data or searching tree or traversing structures. The full form of BFS is the Breadth-first search.

The algorithm efficiently visits and marks all the key nodes in a graph in an accurate breadthwise fashion. This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent to the selected node. Remember, BFS accesses these nodes one by one.

Once the algorithm visits and marks the starting node, then it moves towards the nearest unvisited nodes and analyses them. Once visited, all nodes are marked. These iterations continue until all the nodes of the graph have been successfully visited and marked.

In this Algorithm tutorial, you will learn:

What is Graph traversals?

A graph traversal is a commonly used methodology for locating the vertex position in the graph. It is an advanced search algorithm that can analyze the graph with speed and precision along with marking the sequence of the visited vertices. This process enables you to quickly visit each node in a graph without being locked in an infinite loop.

The architecture of BFS algorithm

  1. In the various levels of the data, you can mark any node as the starting or initial node to begin traversing. The BFS will visit the node and mark it as visited and places it in the queue.
  2. Now the BFS will visit the nearest and un-visited nodes and marks them. These values are also added to the queue. The queue works on the FIFO model.
  3. In a similar manner, the remaining nearest and un-visited nodes on the graph are analyzed marked and added to the queue. These items are deleted from the queue as receive and printed as the result.

Why do we need BFS Algorithm?

There are numerous reasons to utilize the BFS Algorithm to use as searching for your dataset. Some of the most vital aspects that make this algorithm your first choice are:

How does BFS Algorithm Work?

Graph traversal requires the algorithm to visit, check, and/or update every single un-visited node in a tree-like structure. Graph traversals are categorized by the order in which they visit the nodes on the graph.

BFS algorithm starts the operation from the first or starting node in a graph and traverses it thoroughly. Once it successfully traverses the initial node, then the next non-traversed vertex in the graph is visited and marked.

Hence, you can say that all the nodes adjacent to the current vertex are visited and traversed in the first iteration. A simple queue methodology is utilized to implement the working of a BFS algorithm, and it consists of the following steps:

Step 1)

Each vertex or node in the graph is known. For instance, you can mark the node as V.

Step 2)

In case the vertex V is not accessed then add the vertex V into the BFS Queue

Step 3)

Start the BFS search, and after completion, Mark vertex V as visited.

Step 4)

The BFS queue is still not empty, hence remove the vertex V of the graph from the queue.

Step 5)

Retrieve all the remaining vertices on the graph that are adjacent to the vertex V

Step 6)

For each adjacent vertex let's say V1, in case it is not visited yet then add V1 to the BFS queue

Step 7)

BFS will visit V1 and mark it as visited and delete it from the queue.

Example BFS Algorithm

Step 1)

You have a graph of seven numbers ranging from 0 – 6.

Step 2)

0 or zero has been marked as a root node.

Step 3)

0 is visited, marked, and inserted into the queue data structure.

Step 4)

Remaining 0 adjacent and unvisited nodes are visited, marked, and inserted into the queue.

Step 5)

Traversing iterations are repeated until all nodes are visited.

Rules of BFS Algorithm

Here, are important rules for using BFS algorithm:

Applications of BFS Algorithm

Let's take a look at some of the real-life applications where a BFS algorithm implementation can be highly effective.

Summary

 

YOU MIGHT LIKE: