Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in a layer-by-layer fashion. It starts at a designated source vertex and explores all of its neighbor vertices at the current depth level before moving on to vertices at the next depth level.

Unlike tree traversal, graphs can contain cycles. To avoid visiting the same vertex multiple times and getting stuck in an infinite loop, BFS uses a visited tracker (an array or a hash set).

How BFS Works (Step-by-Step)

BFS uses a Queue (First-In-First-Out) data structure to keep track of the vertices that need to be explored.

Visualizing the Graph

Let's perform BFS on the following undirected graph starting from vertex 0:

Trace Table

Step	Current Dequeued Node	Neighbors	Queue Status (Front to Back)	Visited Nodes	Order of Output
Initial	—	—	`[0]`	`{ 0: true }`	—
1	`0`	`1, 2`	`[1, 2]`	`{ 0, 1, 2 }`	`0`
2	`1`	`3, 4`	`[2, 3, 4]`	`{ 0, 1, 2, 3, 4 }`	`0, 1`
3	`2`	`5, 6`	`[3, 4, 5, 6]`	`{ 0, 1, 2, 3, 4, 5, 6 }`	`0, 1, 2`
4	`3`	`7`	`[4, 5, 6, 7]`	`{ 0, 1, 2, 3, 4, 5, 6, 7 }`	`0, 1, 2, 3`
5	`4`	None (already visited)	`[5, 6, 7]`	`{ 0, 1, 2, 3, 4, 5, 6, 7 }`	`0, 1, 2, 3, 4`
6	`5`	None (already visited)	`[6, 7]`	`{ 0, 1, 2, 3, 4, 5, 6, 7 }`	`0, 1, 2, 3, 4, 5`
7	`6`	None (already visited)	`[7]`	`{ 0, 1, 2, 3, 4, 5, 6, 7 }`	`0, 1, 2, 3, 4, 5, 6`
8	`7`	None (already visited)	`[]`	`{ 0, 1, 2, 3, 4, 5, 6, 7 }`	`0, 1, 2, 3, 4, 5, 6, 7`

JavaScript Code Implementation

class Graph {
    constructor() {
        this.list = {};
    }
    
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
    
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2);
        this.list[v2].push(v1);
    }
    
    // Breadth-First Search (BFS) Traversal
    bfs(startNode) {
        const visited = {};
        const queue = [];
        const result = [];
        
        // Mark the start node as visited and enqueue it
        visited[startNode] = true;
        queue.push(startNode);
        
        while (queue.length > 0) {
            // Remove a vertex from the front of the queue
            const currentNode = queue.shift();
            result.push(currentNode);
            
            // Get all adjacent neighbors of the dequeued vertex
            const neighbors = this.list[currentNode] || [];
            for (let neighbor of neighbors) {
                // If a neighbor hasn't been visited, mark it visited and enqueue it
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
        return result;
    }
}
 
// Driver code matching the example
const g = new Graph();
g.addEdge("0", "1");
g.addEdge("0", "2");
g.addEdge("1", "3");
g.addEdge("1", "4");
g.addEdge("2", "5");
g.addEdge("2", "6");
g.addEdge("3", "7");
 
console.log("BFS Traversal:", g.bfs("0").join(" "));
// Output: BFS Traversal: 0 1 2 3 4 5 6 7

Complexity Analysis

Time Complexity: $O(V + E)$
- We visit every vertex exactly once when we dequeue it: $O(V)$.
- For every vertex, we iterate through all of its neighbors (edges): $O(E)$ (specifically, $2E$ for an undirected graph).
Space Complexity: $O(V)$
- The visited object stores up to $V$ keys.
- The queue stores at most $V$ vertices in the worst case (e.g. for a star-shaped graph).

Matrix vs List Comparison Applications of BFS