Breadth First Search (BFS)

Introduction

Breadth First Search (BFS) is one of the most important graph traversal algorithms in computer science and artificial intelligence. Traversal means visiting all the nodes of a graph in a systematic and organized manner.

BFS explores a graph level by level, starting from a given source node. It first visits all the nodes that are closest to the source, and only then moves to nodes that are farther away. Because of this property, BFS is widely used in problems where the shortest path is required.

Definition

Breadth First Search (BFS) is a graph traversal algorithm that starts from a given source node and explores all its adjacent (neighbor) nodes first, before moving to the next level of neighbors. The traversal continues level by level until all nodes are visited.

In simple words:

BFS goes wide first, not deep.

Basic Idea of BFS

The basic idea of BFS is:

• Start from a source node
• Visit all nodes at distance 1 from the source
• Then visit all nodes at distance 2
• Continue this process level by level

This behavior is similar to:

• Ripples in water when a stone is dropped
• Spreading news from one person to all nearby people, then further outward

Data Structure Used

BFS uses a Queue data structure.

• Queue follows FIFO (First In First Out)
• The node that is visited first is processed first

The queue ensures that nodes are explored in the order in which they are discovered, which is essential for level-wise traversal.

Step-by-Step Working of BFS

1. Select a starting (source) node
2. Mark the source node as visited
3. Insert the source node into the queue
4. Remove the front node from the queue
5. Visit all unvisited adjacent nodes of the removed node
6. Mark each adjacent node as visited
7. Insert them into the queue
8. Repeat the process until the queue becomes empty

When the queue is empty, BFS traversal is complete.

Example of BFS Traversal :

Graph Nodes

A, B, C, D, E, F

BFS Traversal (Starting from A)

Step-wise explanation:

1. Start at A
2. Visit neighbors of A → B, C
3. Visit neighbors of B → D, E
4. Visit neighbors of C → F

BFS Traversal Order

A → B → C → D → E → F

This clearly shows that BFS completes one level before moving to the next.

BFS Algorithm (Conceptual Explanation)

• BFS begins with the root or starting node
• All immediate neighbors are visited first
• Nodes are marked as visited to avoid repetition
• The queue maintains the correct visiting order
• The algorithm continues until all reachable nodes are explored

Why BFS Guarantees Shortest Path

BFS always explores:

• Nodes with minimum distance first
• Then nodes with greater distance

In an unweighted graph, this means:

• The first time a node is reached, it is via the shortest path

This makes BFS very important in:

• Shortest path problems
• Navigation systems
• Network routing

Applications of BFS

Breadth First Search is used in:

• Finding shortest path in unweighted graphs
• Web crawling
• Social networking (friend suggestions)
• Network broadcasting
• Artificial Intelligence search problems
• Level-order traversal of trees
• Finding connected components

Advantages of BFS

1. Guarantees shortest path
2. Complete algorithm (will find solution if it exists)
3. Very effective for shallow graphs
4. Easy to understand and implement

Disadvantages of BFS

1. Requires large memory
2. Queue size increases rapidly
3. Not suitable for very deep graphs
4. Inefficient when branching factor is high

Time and Space Complexity

• Time Complexity:
  $O(V + E)$O(V+E)
  where:
  • V = number of vertices
  • E = number of edges
• Space Complexity:
  $O(V)$O(V) due to queue storage

BFS in Artificial Intelligence

In Artificial Intelligence, BFS is used in:

• State space search
• Problem solving
• Planning algorithms

Because BFS is complete and optimal, it is often preferred when:

• A solution is guaranteed to exist
• The shortest solution is required

Conclusion

Breadth First Search is a systematic graph traversal algorithm that explores nodes level by level using a queue. It guarantees the shortest path in unweighted graphs and is widely used in artificial intelligence and network applications. Although BFS requires more memory, its completeness and optimality make it a highly reliable search technique.

ALSO READ – DEPTH FIRST SEARCH (DFS)