BFS Breadth First Search on Graph in DSA C - Time & Space Complexity

Time Complexity: BFS Breadth First Search on Graph

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to explore a graph grows as the graph gets bigger using BFS.

How does the number of steps change when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bfs(int start, int n, int adj[][n]) {
    int visited[n];
    for (int i = 0; i < n; i++) visited[i] = 0;
    int queue[n], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while (front < rear) {
        int node = queue[front++];
        for (int i = 0; i < n; i++) {
            if (adj[node][i] && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
}
    

This code performs a breadth-first search starting from a node, visiting all reachable nodes in the graph.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop that checks all neighbors of the current node.
• How many times: For each node dequeued, it checks all possible nodes to find neighbors.

How Execution Grows With Input

As the graph grows, BFS visits each node once (up to n nodes) and checks all n possible neighbors for each visited node using the adjacency matrix.

Input Size (n)	Approx. Operations
10 nodes	About 10 × 10 = 100 neighbor checks
100 nodes	About 100 × 100 = 10,000 neighbor checks
1000 nodes	About 1000 × 1000 = 1,000,000 neighbor checks

Pattern observation: The work grows quadratically with the number of nodes, O(n²).

Final Time Complexity

Time Complexity: O(n²)

This means BFS (with adjacency matrix) takes time proportional to the square of the number of nodes.

Common Mistake

[X] Wrong: "BFS takes O(n + e) time because it only checks actual edges."

[OK] Correct: The inner loop checks neighbors, but with adjacency matrix, it scans all n possible neighbors per node (n nodes), totaling O(n²) checks even for sparse graphs.

Interview Connect

Understanding BFS time complexity helps you explain graph traversal efficiency clearly, a key skill in many coding challenges and real projects.

Self-Check

"What if the graph is represented using adjacency lists instead of an adjacency matrix? How would the time complexity change?"