Back to Main ACS Page

Module 3: Breadth-First Search

Master the Breadth-First Search algorithm for finding shortest paths in unweighted graphs. Learn how to systematically explore graph levels and track paths efficiently.

Learning Objectives

Core Concepts

Understand BFS algorithm principles
Implement shortest path finding
Track visited nodes efficiently
Handle graph traversal levels

Applications

Social network connections
GPS navigation systems
Web crawling
Network routing protocols

Algorithm Overview

Key Features

Level-by-level exploration
Queue-based implementation
O(V + E) time complexity
Guarantees shortest path

Visual Example

Level 0:            A
                ↙   ↓   ↘
Level 1:      B     C      D
            ↙   ↘        ↙
Level 2:   E      F    G

BFS vs DFS Comparison

Aspect	Breadth-First Search (BFS)	Depth-First Search (DFS)
Data Structure	Queue	Stack (or recursion)
Order of Exploration	Level by level	Path by path
Space Complexity	O(w) where w is the maximum width	O(h) where h is the maximum depth
Time Complexity	O(V + E)	O(V + E)
Best For	Shortest path, nearest neighbor	Path finding, exhaustive search
Applications	Social networks, GPS, web crawling	Puzzles, mazes, topological sorting

Breadth-First Search

1. Breadth-First Search Basics

Key Concepts Explained

Queue Operations

Enqueue: Add to end
Dequeue: Remove from front
FIFO principle
Level order processing

Path Tracking

Parent pointers
Distance tracking
Path reconstruction
Visited set maintenance

BFS Algorithm Steps

Initialize a queue with the start vertex
Mark the start vertex as visited
While the queue is not empty:
- Dequeue a vertex from the queue
- Process the vertex (e.g., add to result)
- For each adjacent vertex that hasn't been visited:
  - Mark it as visited
  - Enqueue it
  - Record its parent for path tracking (optional)

2. Implementing BFS

3. BFS Applications

BFS Implementation

Basic BFS Implementation

/**
 * Performs a breadth-first search on a graph starting from a given vertex
 * @param {Object} graph - Adjacency list representation of the graph
 * @param {string|number} start - The starting vertex
 * @returns {Object} - Contains parent pointers and distances from start
 */
function bfs(graph, start) {
    const queue = [start];
    const visited = new Set([start]);
    const parent = new Map();
    const distance = new Map([[start, 0]]);

    while (queue.length > 0) {
        const vertex = queue.shift();
        
        for (let neighbor of graph[vertex]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
                parent.set(neighbor, vertex);
                distance.set(neighbor, distance.get(vertex) + 1);
            }
        }
    }

    return { parent, distance, visited };
}

Time & Space Complexity

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
- Each vertex is enqueued and dequeued at most once: O(V)
- Each edge is examined at most once: O(E)
Space Complexity: O(V) for the queue, visited set, parent map, and distance map.

Shortest Path Finding

/**
 * Finds the shortest path between two vertices in an unweighted graph
 * @param {Object} graph - Adjacency list representation of the graph
 * @param {string|number} start - The starting vertex
 * @param {string|number} end - The target vertex
 * @returns {Array|null} - Array of vertices forming the path, or null if no path exists
 */
function findShortestPath(graph, start, end) {
    // If start and end are the same, return a single-element path
    if (start === end) {
        return [start];
    }

    const { parent } = bfs(graph, start);
    
    // If end vertex was not reached, return null
    if (!parent.has(end)) {
        return null;
    }

    // Reconstruct the path by following parent pointers backwards
    const path = [];
    let current = end;

    while (current !== undefined) {
        path.unshift(current);
        current = parent.get(current);
    }

    return path;
}

Example Usage:

// Sample graph (adjacency list representation)
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C", "D"));
graph.put("B", Arrays.asList("A", "E"));
graph.put("C", Arrays.asList("A", "F"));
graph.put("D", Arrays.asList("A", "G"));
graph.put("E", Arrays.asList("B"));
graph.put("F", Arrays.asList("C"));
graph.put("G", Arrays.asList("D"));

// Basic BFS traversal
Set<String> visited = bfs(graph, "A").visited;
System.out.println("BFS traversal: " + visited);
// Output: [A, B, C, D, E, F, G]

// Find shortest path from 'A' to 'F'
List<String> path = findShortestPath(graph, "A", "F");
System.out.println("Shortest path from A to F: " + path);
// Output: [A, C, F]

// Find shortest path from 'E' to 'G'
List<String> anotherPath = findShortestPath(graph, "E", "G");
System.out.println("Shortest path from E to G: " + anotherPath);
// Output: [E, B, A, D, G]

Practice Exercises

Exercise 1: Multi-Source BFS

Implement a modified BFS that can start from multiple source nodes simultaneously.

Requirements:

Accept array of starting nodes
Track distance from nearest source
Handle disconnected components
Return distances map

function multiSourceBFS(graph, sources) {
    const queue = [...sources];
    const visited = new Set(sources);
    const distance = new Map();
    
    // Initialize distances for all source nodes
    sources.forEach(source => distance.set(source, 0));
    
    while (queue.length > 0) {
        const vertex = queue.shift();
        
        for (let neighbor of graph[vertex] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
                distance.set(neighbor, distance.get(vertex) + 1);
            }
        }
    }
    
    return { distance, visited };
}

Exercise 2: Path with Conditions

Find shortest path that satisfies certain conditions (e.g., must pass through specific nodes).

Example:

const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};

// Find path from A to F that passes through E
console.log(findPathThroughNode(graph, 'A', 'F', 'E'));
// Output: ['A', 'B', 'E', 'F']

Exercise 3: Level Groups

Group nodes by their levels (distances) from the start node.

Expected Output Format:

const levels = groupByLevels(graph, 'A');
/*
{
    0: ['A'],
    1: ['B', 'C', 'D'],
    2: ['E', 'F', 'G']
}
*/

LeetCode Practice Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are excellent for practicing BFS algorithms.

Beginner BFS Problems:

Flood Fill - Apply a simple BFS to update connected pixels
Number of Islands - Find connected components using BFS
Rotting Oranges - Apply multi-source BFS to simulate rotting process

Shortest Path Problems:

Word Ladder - Find shortest transformation sequence
Shortest Path in Binary Matrix - Find shortest path in a grid
Open the Lock - Find minimum rotations to open a lock

Graph Topology Problems:

Course Schedule - Determine if courses can be finished
Minimum Height Trees - Find tree roots with minimum height
Keys and Rooms - Determine if all rooms can be visited

Advanced BFS Problems:

Word Ladder II - Find all shortest transformation sequences
Minimum Genetic Mutation - Find shortest gene mutation path
Cut Off Trees for Golf Event - Find minimum steps to cut all trees
Sliding Puzzle - Solve sliding puzzle in minimum moves