Breadth First Search (BFS)

BFS is a graph traversal algorithm that explores vertices level by level.

Starting from a source node, it visits all its immediate neighbors first, then their neighbors, and so on like expanding in waves.

It uses a Queue (FIFO) data structure and is especially suitable for finding shortest paths in unweighted graphs.

Key Concepts of Breadth First Search

• Traverses level-wise from the starting node.
• Uses a queue to keep track of the next node to explore.
• Uses a visited list (or array) to avoid cycles or repeated visits.
• Works on both undirected and directed graphs.
• Finds shortest path (in terms of edges) in unweighted graphs.

How Breadth First Search Works?

1. Start from the source node.
2. Mark the source node as visited.
3. Enqueue the source node into a queue.
4. While the queue is not empty:
   1. Dequeue the front node.
   2. Visit all its unvisited neighbors.
   3. Mark them as visited and enqueue them.
5. Repeat until the queue is empty.

Example: Breadth First Search

Given Graph is,

A -- B -- D
|    |
C    E

Adjacency List (Edges)

A: [B, C]
B: [A, D, E]
C: [A]
D: [B]
E: [B]

Breadth First Search Traversal from Vertex A

1. Queue: [A] → Visit A → Enqueue B, C
2. Queue: [B, C] → Visit B → Enqueue D, E
3. Queue: [C, D, E] → Visit C (already visited A)
4. Queue: [D, E] → Visit D
5. Queue: [E] → Visit E
6. Queue: [] → Done

Algorithm for Breadth First Search (BFS)

Input: A graph G(V, E) and a starting node s.

Output: The order of traversal from node s using BFS.

BFS Algorithm Steps:

1. Create an empty queue Q.
2. Create a visited array or list to keep track of visited nodes.
3. Mark the starting node s as visited and enqueue it into Q.
4. While Q is not empty:
   • Dequeue a node u from the front of the queue.
   • Process node u (e.g., print or store it).
   • For each unvisited neighbor v of u:
     • Mark v as visited.
     • Enqueue v into Q.

Time and Space Complexity

Let,

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

Time Complexity: O(V + E) each node and edge is visited once.

Space Complexity: O(V) for the visited array and queue.

Applications of Breadth First Search

• Finding shortest path in unweighted graphs (e.g., maps, networks).
• Crawling the web (pages = nodes, links = edges).
• Social network analysis (e.g., finding people within n degrees).
• Broadcasting in networks.
• Maze solving and robot navigation.

Advantages of Breadth First Search

Finds the Shortest Path

In unweighted graphs, BFS always finds the shortest path (fewest edges) from the source to any reachable node.

Simple and Systematic

Easy to understand and implement using a queue and visited array.

Works Well for Closest Node Problems

Ideal for scenarios where the goal is near the starting point, like shortest distance, minimum hops, etc.

Useful in Real-world Applications

Used in web crawling, social networking, network broadcasting, and AI (like solving puzzles and mazes).

Complete Algorithm

If a solution exists, BFS is guaranteed to find it (unlike greedy or DFS which may get stuck).

Disadvantages of Breadth First Search

High Memory Usage

Uses a queue and visited list can consume lots of memory in wide/deep graphs (especially with many nodes at the same level).

Can Be Slow on Large Graphs

It explores all neighbors level-by-level, which may lead to longer processing time for very large graphs.

Doesn’t Work for Weighted Graphs

Cannot find the shortest path correctly in weighted graphs; for that, Dijkstra’s Algorithm is preferred.

Queue Can Grow Large

If the branching factor is high (many neighbors), the queue can become very large and inefficient.

Not Suitable for Recursive Implementation

Unlike DFS, BFS is hard to implement using recursion because it depends on a queue, not a stack.

BFS vs DFS

Numerical Questions for Breadth First Search

1. Given the following graph (undirected), perform BFS traversal starting from vertex A.

• Vertices: A, B, C, D, E
• Edges: A–B, A–C, B–D, C–E

Expected Output is BFS traversal order.

2. You are given this adjacency list of a directed graph:

• Graph: 0 → [1, 2] 1 → [2, 3] 2 → [4] 3 → [] 4 → []

Perform BFS starting from node 0. Output the order of nodes visited.

3. Given the following graph, determine whether all nodes are reachable from node 1 using BFS.

• Graph: 1 → 2 2 → 3 3 → 4 4 → 5 5 → 1 6 → 7

Is node 6 reachable from node 1?

4. Given an undirected graph:

• Vertices: 1, 2, 3, 4, 5, 6
• Edges: 1–2, 1–3, 2–4, 3–5, 4–6

Perform BFS traversal from node 1. Also, track the level of each node (i.e., how far it is from node 1).

5. In an unweighted undirected graph:

• Vertices: A, B, C, D, E
• Edges: A–B, A–C, B–D, C–D, D–E

Using BFS, find the shortest path (in terms of number of edges) from node A to E.