BFS Algorithm

Introduction to BFS Algorithm

To access and manage the data efficiently, it can be stored and organized in a special format known as the data structure. There are many data structures such as Stack, Array, Linked List, Queues, Trees, and Graphs etc. In linear data structures, such as Stack, Array, Linked List and Queue, the data is organized in linear order whereas, in non-linear data structures like Trees and Graphs, data is organized hierarchically not in a sequence. The graph is a non-linear data structure which has nodes and edges. Nodes in Graph can also be referred to as vertices which are finite in number and edges are the connecting lines between any two nodes.

In the above graph, vertices can be represented as V = {A, B, C, D, E} and edges can be defined as

E = {AB, AC, CD, BE}

What is the BFS Algorithm?

There are generally two algorithms which are used for traversal of a graph. They are BFS (Breadth-First Search) and DFS (Depth First Search) algorithms. Traversal of the Graph is visiting exactly once each vertex or node and edge, in a well-defined order. Also, it is very important to keep track of the vertices those have been visited so that the same vertex is not traversed twice. In Breath First Search algorithm, the traversing starts from a selected node or source node and the traversal continues through the nodes directly connected to the source node. In simpler terms, in BFS algorithm one should first horizontally move and traverse the current layer after which moved to the next layer should be done.

How does BFS Algorithm Works?

Let us take the example of the below graph.

The important task at hand is to find the shortest path in a graph while traversing the nodes. When we traverse through a graph, the vertex goes from undiscovered state to discovered state and finally becomes completely discovered. It is to be noted that it is possible to get stuck at some point while traversing through a graph and a node can be visited twice. So we can employ a method of marking the nodes after it changes the state of being undiscovered to being completely discovered.

We can see in the below image that the nodes can be marked in the graphs as they become completely discovered by marking them with black. We can start at the source node and as the traversal progresses through each node, they can be marked to be identified.

The traversal starts from a vertex and then travels to the outgoing edges. When an edge goes to an undiscovered vertex, it is marked as discovered. But when an edge goes to a completely discovered or discovered vertex, it is ignored.

For a directed graph, each edge is visited once and for undirected graph, it is visited twice i.e. once while visiting each node. The algorithm to be used is decided on the basis of how the discovered vertices are stored. In the BFS algorithm, the queue is used where the oldest vertex is discovered first and then propagates through the layers from the starting vertex.

Steps are Performed for a BFS Algorithm

The below steps are performed for a BFS algorithm.

• In a given graph, let us start from a vertex i.e. in the above diagram it is node 0. The level, in which this vertex is present, can be denoted as Layer 0.
• Next step is to find all the other vertices that are adjacent to the starting vertex i.e. node 0 or immediately accessible from it. Then we can mark these adjacent vertices to be present at Layer 1.
• It is possible to come to the same vertex due to a loop in the graph. So, we should travel only to those vertices which should be present in the same layer.
• Next, the parent vertex of the current vertex that we are at is marked. Same is to be performed for all the vertices at Layer 1.
• Then the next step is to find all those vertices those are a single edge away from all the vertices which are at Layer 1. These new set of vertices will be at Layer 2.
• The above process is repeated until all the nodes are traversed.

Example:

Let us take the example of the below graph and understand how the BFS algorithm works. Generally, in a BFS algorithm, a queue is used to en-queue the nodes while traversing the nodes.

In the above graph, first the node 0 is to be visited and this node is en-queued to the below queue:

After visiting the node 0, the neighbouring node of 0, 1 and 2 are en-queued. The queue can be represented as below:

Then the first node in the queue which is 2 will be visited. After the node 2 is visited, the queue can be represented as below:

After visiting the node 2, 5 will be en-queued and as there are no unvisited neighbouring nodes for node 5, still though 5 is en-queued but it will not be visited twice.

Next, the first node in the queue is 1 which will be visited. The neighbouring nodes 3 and 4 are en-queued. The queue is represented as below

Next, the first node in the queue is 5, and for this node, there are no more unvisited neighbouring nodes. The same goes for nodes 3 and 4 for which there are no more unvisited neighbouring nodes too.

So all the nodes are traversed and finally, the queue becomes empty.

Conclusion

Breadth Search Algorithm comes with some great advantages to recommend it. One of the many applications of the BFS algorithm is to calculate the shortest path. Also, it is used in networking to find neighbouring nodes and can be found in social networking sites, network broadcasting and garbage collection. The users need to understand the requirement and the data pattern to use it for better performance.

Recommended Articles

This has been a guide to the BFS Algorithm. Here we discuss the concept, working, steps and example of performance in BFS Algorithm. You can also go through our other Suggested Articles to learn more –

1. What is a Greedy Algorithm?
2. Ray Tracing Algorithm
3. Digital Signature Algorithm
4. What is Java Hibernate?