Connected Components Using BFS in DSA C - Time & Space Complexity

Time Complexity: Connected Components Using BFS

O(n^2)

Understanding Time Complexity

We want to understand how long it takes to find all connected parts in a graph using BFS.

How does the time needed grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bfs(int start, int n, int adj[][n], int visited[]) {
    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;
            }
        }
    }
}

int countConnectedComponents(int n, int adj[][n]) {
    int visited[n];
    for (int i = 0; i < n; i++) visited[i] = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i, n, adj, visited);
            count++;
        }
    }
    return count;
}
    

This code finds how many connected groups are in a graph using BFS traversal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: BFS visits each node and checks all its possible neighbors (scans matrix row).
• How many times: Each node is visited once, and for each node all n possible neighbors are checked.

How Execution Grows With Input

As the graph grows, BFS processes all n nodes and scans n rows of the matrix (n checks each).

Input Size (n)	Approx. Operations
10 nodes	About 100 (n2)
100 nodes	About 10,000 (n2)
1000 nodes	About 1,000,000 (n2)

Pattern observation: The work grows roughly with the square of the number of nodes.

Final Time Complexity

Time Complexity: O(n2)

This means the time grows quadratically with the number of nodes (for adjacency matrix).

Common Mistake

[X] Wrong: "BFS takes O(n) time because each node is visited once."

[OK] Correct: Node visits are O(n), but neighbor checks scan O(n) matrix entries per node, totaling O(n²).

Interview Connect

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

Self-Check

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