Breadth First Search (BFS)

Definition

Breadth First Search (BFS) is a graph traversal algorithm that starts from a source vertex and explores all vertices at the current distance level before moving to vertices at the next distance level, typically using a queue data structure to maintain the order of traversal.

Main Content

1. Graph Traversal in Breadth-First Order

• BFS visits vertices level by level, beginning from a source node and then moving to all its immediate neighbors, followed by neighbors of those neighbors.
• This traversal strategy ensures that every node is explored in order of its distance from the starting vertex.

In a graph, a vertex may have multiple adjacent vertices. BFS does not go deep along one path like Depth First Search; instead, it spreads outward in layers. For example, if we start at vertex A, BFS will first visit all vertices directly connected to A, then all vertices connected to those vertices, and so on. This makes BFS ideal for problems where the shortest number of edges matters.

Example graph:

        A
      / | \
     B  C  D
    / \      \
   E   F      G

If BFS starts from A, the traversal order is:

A → B → C → D → E → F → G

This order reflects the level structure:

• Level 0: A
• Level 1: B, C, D
• Level 2: E, F, G

2. Queue-Based Exploration Mechanism

• BFS uses a queue to store vertices that have been discovered but not yet fully explored.
• The queue follows FIFO (First In, First Out) order, which ensures that vertices are processed in the same order they are discovered.

The queue is the heart of BFS. When a vertex is visited, all its unvisited neighbors are added to the queue. The vertex at the front of the queue is then removed and processed. This prevents BFS from skipping to deeper levels prematurely.

A simple view of queue behavior:

Start:   [A]
Visit A, enqueue neighbors B, C, D
Queue:   [B, C, D]
Visit B, enqueue E, F
Queue:   [C, D, E, F]
Visit C
Queue:   [D, E, F]
...

This queue-driven process guarantees that BFS explores every vertex at a given depth before advancing to the next depth.

3. Visited Tracking and Shortest Path Property

• BFS maintains a visited array/set to avoid revisiting vertices and getting stuck in cycles.
• In an unweighted graph, BFS finds the shortest path in terms of number of edges from the source to every reachable vertex.

Without visited tracking, BFS could repeatedly enqueue the same vertex in graphs containing cycles, causing inefficiency or infinite loops. Marking vertices as visited when they are discovered ensures each vertex is processed at most once.

A major advantage of BFS is that the first time a vertex is reached, it is reached through the shortest possible path from the source in an unweighted graph. For example, if there are two ways to reach G, one with 2 edges and another with 4 edges, BFS will discover the 2-edge path first because it explores level by level.

This property makes BFS extremely useful in:

• shortest path in unweighted networks,
• minimum move problems in puzzles,
• connectivity and reachability analysis.

Working / Process

1. Choose a starting vertex and mark it as visited.

Insert the starting vertex into the queue. This vertex becomes the source of the traversal.

2. Remove a vertex from the front of the queue and process it.

After processing the current vertex, inspect all of its adjacent vertices.

3. Enqueue all unvisited neighbors and repeat until the queue is empty.

Mark each newly discovered neighbor as visited before adding it to the queue to prevent repeated processing.

A typical BFS procedure can be represented as follows:

1. Create an empty queue.
2. Mark the starting node visited.
3. Enqueue the starting node.
4. While the queue is not empty:
   a. Dequeue the front node.
   b. Visit it / process it.
   c. For every adjacent node:

      - If not visited, mark visited
      - Enqueue it

Example traversal from A:

Graph:
        A
      / | \
     B  C  D
    / \      \
   E   F      G

Step-by-step:

• Start with A in queue
• Dequeue A, enqueue B, C, D
• Dequeue B, enqueue E, F
• Dequeue C, no new node
• Dequeue D, enqueue G
• Dequeue E, F, G

Traversal order:

A, B, C, D, E, F, G

This process is simple but highly systematic, making BFS one of the most reliable traversal methods for graph problems.

Advantages / Applications

Finds shortest paths in unweighted graphs.

BFS is the standard technique for determining the minimum number of edges between two vertices when edge weights are equal or absent.

Useful for level-order exploration and distance-based problems.

It naturally groups vertices by distance from the source, which is valuable in tree level traversal, broadcasting, and layered network analysis.

Widely applied in real-world problem solving.

BFS is used in web crawling, social network friend suggestions, routing, connected component detection, puzzle solving, and maze/pathfinding tasks.

Summary

• BFS is a graph traversal method that explores nodes level by level using a queue.
• It is especially effective for unweighted shortest path and connectivity problems.
• The main terms to remember are: queue, visited, level, source vertex, unweighted graph