Bird
Raised Fist0
DSA Cprogramming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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 nodesAbout 100 (n2)
100 nodesAbout 10,000 (n2)
1000 nodesAbout 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(n2).

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?"

Practice

(1/5)
1. What does the BFS algorithm help find in an undirected graph when used to find connected components?
easy
A. All nodes reachable from a starting node forming one connected component
B. The shortest path between two nodes only
C. The number of edges in the graph
D. The degree of each node

Solution

  1. Step 1: Understand BFS traversal in undirected graphs

    BFS explores all nodes reachable from a given start node by visiting neighbors level by level.

  2. Step 2: Connect BFS to connected components

    By running BFS from an unvisited node, we find all nodes in that node's connected component.

  3. Final Answer:

    All nodes reachable from a starting node forming one connected component -> Option A

  4. Quick Check:

    BFS finds connected components by exploring reachable nodes [OK]
Hint: BFS visits all nodes in one connected component [OK]
Common Mistakes:
  • Thinking BFS only finds shortest paths
  • Confusing connected components with edge counts
  • Assuming BFS finds node degrees
2. Which of the following is the correct way to mark a node as visited in BFS when using an array named visited and current node u?
easy
A. visited[u] = 0;
B. visited[u] = true;
C. visited[u] == true;
D. visited[u] = null;

Solution

  1. Step 1: Understand marking visited nodes

    To mark a node visited, assign true to visited[u], indicating it is visited.

  2. Step 2: Check syntax correctness

    Using visited[u] = true; correctly assigns the boolean true. Using == is a comparison, not assignment.

  3. Final Answer:

    visited[u] = true; -> Option B

  4. Quick Check:

    Assign true to mark visited[u] [OK]
Hint: Use assignment (=), not comparison (==), to mark visited [OK]
Common Mistakes:
  • Using == instead of = for assignment
  • Assigning 0 instead of true to visited
  • Assigning null which is invalid in C
3. Given the following graph adjacency list and BFS code snippet, what is the output number of connected components? 
int n = 5;
int adj[5][5] = {
  {0,1,0,0,0},
  {1,0,0,0,0},
  {0,0,0,1,1},
  {0,0,1,0,0},
  {0,0,1,0,0}
};
bool visited[5] = {false};

int count = 0;
for (int i = 0; i < n; i++) {
  if (!visited[i]) {
    bfs(i, adj, visited, n);
    count++;
  }
}
printf("%d\n", count);
medium
A. 2
B. 1
C. 3
D. 4

Solution

  1. Step 1: Analyze adjacency matrix for connected components

    Nodes 0 and 1 are connected; nodes 2, 3, 4 form another connected group.

  2. Step 2: Count connected components using BFS

    BFS from node 0 visits nodes 0 and 1; BFS from node 2 visits nodes 2, 3, 4. Total components = 2.

  3. Final Answer:

    2 -> Option A

  4. Quick Check:

    Two groups found by BFS = 2 [OK]
Hint: Count BFS runs on unvisited nodes for components [OK]
Common Mistakes:
  • Counting edges instead of components
  • Misreading adjacency matrix connections
  • Forgetting to mark visited nodes
4. Identify the bug in this BFS function for counting connected components: 
void bfs(int start, int adj[][5], bool visited[], int n) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = 0; v < n; v++) {
      if (adj[u][v] == 1 && visited[v] == false) {
        q.push(v);
      }
    }
  }
}
medium
A. Loop condition should be while(q.size() > 1)
B. Queue is not initialized properly
C. Start node is not marked visited
D. Missing visited[v] = true; inside the loop

Solution

  1. Step 1: Check BFS neighbor processing

    When a neighbor v is found unvisited, it must be marked visited immediately to avoid re-adding.

  2. Step 2: Identify missing visited mark

    The code pushes v to queue but does not mark visited[v] = true; causing repeated visits.

  3. Final Answer:

    Missing visited[v] = true; inside the loop -> Option D

  4. Quick Check:

    Mark visited when enqueueing neighbors [OK]
Hint: Mark visited when pushing to queue, not after popping [OK]
Common Mistakes:
  • Marking visited only after popping from queue
  • Incorrect queue initialization
  • Wrong loop condition for BFS
5. You have a graph with 7 nodes and edges: (0-1), (1-2), (3-4), (5-6). Using BFS to find connected components, what is the minimum number of BFS calls needed to find all components?
hard
A. 1
B. 2
C. 3
D. 4

Solution

  1. Step 1: Identify connected components from edges

    Edges connect nodes into groups: {0,1,2}, {3,4}, {5,6}. Since nodes are numbered 0 to 6, there are no other nodes.

  2. Step 2: Count connected components

    Groups are: {0,1,2}, {3,4}, {5,6} -> 3 components total.

  3. Step 3: BFS calls equal connected components

    Each BFS call finds one component, so minimum BFS calls = 3.

  4. Final Answer:

    3 -> Option C

  5. Quick Check:

    Number of BFS calls = number of connected components [OK]
Hint: Count connected groups; BFS calls = groups [OK]
Common Mistakes:
  • Counting edges instead of components
  • Miscounting isolated nodes
  • Assuming BFS calls equal nodes
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard