Breadth First Search Algorithm

In this article Breadth First Search Algorithm (BFS) is a graph traversal algorithm that explores vertices level by level using a queue. Learn BFS algorithm, pseudocode, example, time complexity, applications, advantages, and limitations in a simple and clear way.

Breadth First Search Algorithm: 

Introduction

Breadth First Search (BFS) is a graph traversal algorithm used to explore vertices of a graph.

In BFS, vertices are visited level by level.
Starting from a given source vertex, all its adjacent vertices are visited first, then the algorithm moves to the next level.

Data Structure Used in BFS

BFS uses a Queue (FIFO – First In First Out) data structure.

The queue ensures that vertices are processed in the same order in which they are discovered.

How BFS Algorithm Works

1. Insert the starting vertex into the queue
2. Mark the starting vertex as visited
3. Remove a vertex from the queue and visit all its unvisited adjacent vertices
4. Mark each adjacent vertex as visited and insert it into the queue
5. Repeat the process until the queue becomes empty

BFS Algorithm ( Pseudo Code )

BFS(G, s)

create empty queue Q

mark s as visited

enqueue(Q, s)

while Q is not empty

u = dequeue(Q)

for each vertex v adjacent to u

if v is not visited

mark v as visited

enqueue(Q, v)

Example

If A is the source vertex, then the BFS traversal order will be:

A → B → C → D → E

(First all vertices at the current level are visited, then the next level is processed.)

Features of BFS

• Performs level-wise traversal
• Finds the shortest path in an unweighted graph
• Each vertex is visited only once
• Uses a queue for traversal

Time and Space Complexity

• Time Complexity: O ( V + E )
• Space Complexity: O ( V )

Where:

• V = number of vertices
• E = number of edges

Applications of BFS

• Finding the shortest path in an unweighted graph
• Discovering connections in social networks
• Web crawling
• Network broadcasting
• Detecting connected components

Advantages and Limitations of BFS

Advantages:

• Simple and easy to understand
• Guarantees the shortest path in unweighted graphs
• Complete traversal of the graph

Limitations:

• Requires more memory due to queue storage
• Not suitable for weighted graphs
• Can be slow for very large graphs

Conclusion

Breadth First Search ( BFS ) is an effective graph traversal algorithm that explores vertices level by level using a queue.
It is especially useful for finding the shortest path in unweighted graphs and for applications requiring systematic exploration.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1