Breadth First Search (BFS)
Graph traversal is a way to explore all the points (vertices) in a network (graph).
It helps us find specific points and decide the best order to visit them, making
sure we don't go in circles (loops).
There are two main methods:
o Breadth-First Search (BFS) and Depth-First Search (DFS).
Breadth-First Search Algorithm or BFS is the most widely utilized method.
BFS is a graph traversal approach in which you start at a source node and layer
by layer through the graph, analyzing the nodes directly related to the source
node. Then, in BFS traversal, you must move on to the next-level neighbor
nodes.
According to the BFS, you must traverse the graph in a breadthwise direction:
To begin, move horizontally and visit all the current layer's nodes.
Continue to the next layer.
Breadth-First Search uses a queue data structure to store the node and mark it
as "visited" until it marks all the neighbouring vertices directly related to it.
The queue operates on the First In First Out (FIFO) principle, so the node's
neighbours will be viewed in the order in which it inserts them in the node,
starting with the node that was inserted first.
How Does the BFS Algorithm Work?
Breadth-First Search uses a queue data structure technique to store the vertices. And
the queue follows the First In First Out (FIFO) principle, which means that the
neighbours of the node will be displayed, beginning with the node that was put first.
The transverse of the BFS algorithm is approaching the nodes in two ways.
Visited node
Not visited node
How Does the Algorithm Operate?
Start with the source node.
Add that node at the front of the queue to the visited list.
Make a list of the nodes as visited that are close to that vertex.
And dequeue the nodes once they are visited.
Repeat the actions until the queue is empty.
The Architecture of the BFS Algorithm
We understand the architecture of BFS and how the algorithm visits nodes in the tree
diagram, which is added below.
The above tree diagram contains three layers, which are numbered from 0 to 2.
We are allowed to use any node as our source node as per the law. However, in this
case, we can use 0 as our source node.
Then we explore breadthwise and find the nodes which are adjacently connected to
our source node.
Then we must come down to layer two and find the relative nodes that are adjacent
to the layer 1 nodes.
If you select the alternative source node, this order will change. And that's how the
straightforward BFS algorithm operates.
BFS ALGORITHM
Breadth_First_Serach( G, A )
q.enqueue( A )
While ( q is not empty )
B = q.dequeue( )
For all neighbors of C of B
If C is not visited, q. enqueue( C )
Mark C a visited
Example
step 1: In the graph, every vertex or node is known. First, initialize a queue.
Step 2: In the graph, start from source node A and mark it as visited
Step 3: Then you can observe B and E, which are unvisited nearby nodes from A. You
have two nodes in this example, but here choose B, mark it as visited, and enqueue it
alphabetically.
Step 4: Node E is the next unvisited neighboring node from A. You enqueue it after
marking it as visited.
Step 5: A now has no unvisited nodes in its immediate vicinity. As a result, you
dequeue and locate A.
Step 6: Node C is an unvisited neighboring node from B. You enqueue it after
marking it as visited.
Step 7: Node D is an unvisited neighboring node from C. You enqueue it after
marking it as visited.
Step 8: If all of D's adjacent nodes have already been visited, remove D from
the queue.
Step 9: Similarly, all nodes near E, B, and C nodes have already been visited;
therefore, you must remove them from the queue.
