Shortest Path in Unweighted Graph Using BFS in DSA C - Time & Space Complexity

Time Complexity: Shortest Path in Unweighted Graph Using BFS

O(n + m)

Understanding Time Complexity

We want to understand how long it takes to find the shortest path in an unweighted graph using BFS.

How does the time grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bfsShortestPath(int start, int n, vector<vector<int>> &adj) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
    

This code finds the shortest distance from a start node to all other nodes in an unweighted graph using BFS.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node and checking its neighbors.
• How many times: Each node is visited once, and each edge is checked once.

How Execution Grows With Input

As the graph grows, the time to visit nodes and edges grows roughly with the number of nodes plus edges.

Input Size (n)	Approx. Operations
10 nodes, 15 edges	About 25 operations (10 nodes + 15 edges)
100 nodes, 200 edges	About 300 operations (100 + 200)
1000 nodes, 5000 edges	About 6000 operations (1000 + 5000)

Pattern observation: The operations grow linearly with the number of nodes and edges combined.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total number of nodes (n) and edges (m) in the graph.

Common Mistake

[X] Wrong: "BFS takes O(n²) time because it uses nested loops."

[OK] Correct: BFS visits each node and edge only once, so it does not check all pairs of nodes. The loops are over neighbors, not all nodes.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches scale and why BFS is efficient for shortest paths in unweighted graphs.

Self-Check

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