Breadth-First Search (BFS)

# CHAPTER 23

Breadth-First Search (BFS) #

1. Introduction #

2. Learning Objectives #

• Explain the "Level-by-Level" wave traversal pattern.

• Implement the mandatory Queue data structure.

• Understand the critical importance of the Visited Boolean Array.

• Analyze the $O(V + E)$ Time Complexity limits.

• Apply BFS to Shortest-Path problems.

3. The Execution Logic #

1. 1. The Queue (FIFO): Dictates the exact chronological order of exploration.

1. 2. The Visited Array: A massive checklist. If a Node is marked "Visited", the algorithm ignores it, mathematically preventing infinite loops.

The Mechanics (Level-by-Level):

1. 1. Start at a Root Node (e.g., Node 0). Mark it Visited. Push it into the Queue.

1. 2. Dequeue the front Node.

1. 3. Look at all its immediate Neighbors.

1. 4. If a Neighbor is NOT Visited, mark it Visited and push it into the Queue!

1. 5. Repeat until the Queue is entirely empty.

4. Implementation in Code #

// Java Example: Breadth-First Search using an Adjacency List
import java.util.*;

public class GraphBFS {
    
    // We assume the graph is represented as an Array of Lists
    public void BFS(int startNode, List<List<Integer>> adjList, int totalVertices) {
        
        // 1. The Visited Array (Defaults to false)
        boolean[] visited = new boolean[totalVertices];
        
        // 2. The Queue (FIFO architecture)
        Queue<Integer> queue = new LinkedList<>();
        
        // 3. Initialize the starting node
        visited[startNode] = true;
        queue.add(startNode);
        
        // 4. The Core Traversal Loop
        while (!queue.isEmpty()) {
            
            // Extract the node at the front of the line
            int currentNode = queue.poll();
            System.out.print(currentNode + " ");
            
            // Iterate through ALL immediate neighbors of the current node
            for (int neighbor : adjList.get(currentNode)) {
                
                // If we haven't seen this neighbor before...
                if (!visited[neighbor]) {
                    // Mark it visited instantly to prevent loop traps!
                    visited[neighbor] = true; 
                    // Add it to the back of the queue to be explored later
                    queue.add(neighbor);
                }
            }
        }
    }
}

5. Why Queue (FIFO)? #

6. Complexity Analysis #

7. BFS: The Shortest Path Engine #

• Level 1: 1 jump away.

• Level 2: 2 jumps away.

• Level 3: 3 jumps away.

8. Real-World Applications #

1. 1. Social Networks (LinkedIn/Facebook): When LinkedIn tells you a user is a "2nd Degree Connection" or "3rd Degree Connection", it is natively executing a localized BFS wave outward from your profile node.

1. 2. Peer-to-Peer Networks (BitTorrent): P2P software utilizes BFS to broadcast file discovery queries sequentially to neighboring nodes in the decentralized network grid.

1. 3. Web Crawlers: Googlebot starts at a root webpage, extracts all hyperlinks (edges), and queues them into a BFS engine to systematically map the internet.

9. Common Mistakes #

• Marking Nodes Visited AFTER Dequeuing: A critical beginner mistake is pushing neighbors into the queue, but waiting until they are Dequeued to mark them Visited. This causes the algorithm to accidentally push the same node into the queue 50 times from different angles, detonating memory limits. You MUST mark a node Visited the exact millisecond you push it into the queue!

10. Exercises #

1. 1. Draw a simple graph: A connected to B and C. B connected to D. C connected to D. Trace the exact contents of the Queue step-by-step for a BFS starting at A.

1. 2. Why is BFS completely mathematically invalid for calculating the "Shortest Path" if the edges have different weights (e.g., Highway A is 5 miles, Highway B is 100 miles)?

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Adaptation:* "How do you calculate the exact shortest path *distance* during a BFS?" *(Answer: Instead of a flat Visited boolean array, deploy an integer Distance array initialized to -1. When exploring a new neighbor, instead of just marking true, set Distance[neighbor] = Distance[current] + 1. The array organically maps the exact step count from the root to every single node!).*

13. Summary #

14. Next Chapter Recommendation #