What Determines BFS Runtime?
Breadth-first search (BFS) is often summarized as taking \(O(n+m)\) time, where \(n\) is the number of vertices and \(m\) is the number of edges. That bound describes the usual adjacency-list implementation when all vertices are processed. It is not a representation-free rule: an adjacency matrix makes BFS inspect positions that do not represent edges. Initialization also matters. Even if the search reaches only a few vertices, an implementation that initializes an array for every vertex still performs work proportional to \(n\).
Throughout, \(G=(V,E)\) is a finite simple directed graph, \(n=|V|\), and \(m=|E|\). An edge \(uv\) is an arc from \(u\) to \(v\). We assume \(n\ge 1\) and start BFS at a source \(s\in V\). For an adjacency list, each vertex stores a list of its outgoing neighbors. For an adjacency matrix, rows and columns are indexed by vertices, and the entry in row \(u\), column \(v\) is \(1\) exactly when \(uv\in E\), and \(0\) otherwise.
We use the standard BFS implementation: initialize a state, distance and parent entry for every vertex; mark \(s\) discovered with distance \(0\); and use a first-in, first-out queue. When a vertex is removed from the queue, inspect its outgoing neighbors. Each undiscovered neighbor is marked immediately, assigned a parent and distance, and enqueued. Each vertex is enqueued and removed at most once. Earlier material on BFS establishes that this procedure visits exactly the vertices in \(R\) and assigns their unweighted distances from \(s\). Here the focus is how much work the implementation performs.
Counting the Operations
Assume each array access, state test, and queue operation takes constant time. The initialization loop writes the entries for all \(n\) vertices, so it takes \(\Theta(n)\) time. The source setup and queue setup take constant time in addition to that loop.
With adjacency lists, processing a reached vertex \(u\) scans its outgoing list once. The total number of list entries scanned is therefore \(m_R\): every arc with tail in \(R\) is scanned once, and no list for a vertex outside \(R\) is scanned. The queue operations and the per-vertex processing contribute \(\Theta(n_R)\) work. Thus the total, including array initialization, is \(\Theta(n+n_R+m_R)\).
With an adjacency matrix, processing \(u\) scans all \(n\) entries in row \(u\), testing which entries equal \(1\). There is one such row scan for each of the \(n_R\) reached vertices, for \(n n_R\) entry tests altogether. Including initialization and per-vertex work, the total is \(\Theta(n+n n_R)\). The number of edges does not replace \(n\) in a row scan: zero entries are tested too.
Proof. The initialization loop writes a constant number of entries for each of the \(n\) vertices, requiring \(\Theta(n)\) operations. During BFS, each vertex in \(R\) is enqueued and removed once, requiring \(\Theta(n_R)\) queue operations, and each reached vertex incurs constant overhead when processed. With adjacency lists, exactly the outgoing list entries of vertices in \(R\) are inspected, for \(m_R\) inspections. The total is therefore \(\Theta(n+n_R+m_R)\). With an adjacency matrix, each of the \(n_R\) processed vertices causes all \(n\) entries of its row to be inspected, for \(n n_R\) inspections; together with initialization and per-vertex work this is \(\Theta(n+n n_R)\). These counts are both upper and lower bounds for this implementation because the stated initialization entries and neighbor entries are actually visited. If \(R=V\), then \(n_R=n\) and \(m_R=m\), giving \(\Theta(n+m)\) and \(\Theta(n+n^2)=\Theta(n^2)\). \(\square\)
The theorem concerns the search on a graph whose representation is already available. If constructing the representation is part of the task, add that cost. Creating \(n\) empty adjacency lists and inserting \(m\) arcs takes \(\Theta(n+m)\) time. Creating an \(n\)-by-\(n\) matrix requires \(\Theta(n^2)\) entries to be initialized, after which the arcs are recorded. For a simple directed graph, \(m\le n^2\), so this construction takes \(\Theta(n^2)\) time overall.
Worked Operation Counts
Worked Example: Adjacency Lists on a Partly Reached Graph
Let \(V=\{s,a,b,c,d,e\}\) and \(E=\{sa,sb,ac,bc,ca,de\}\). Store the outgoing neighbors as lists: \(s:[a,b]\), \(a:[c]\), \(b:[c]\), \(c:[a]\), \(d:[e]\), and \(e:[]\). Start BFS at \(s\). The list is initialized for all six vertices, but only \(s,a,b,c\) are reached.
| Action | Queue after action | Newly discovered | Outgoing entries scanned |
|---|---|---|---|
| Initialize; enqueue \(s\) | \([s]\) | \(s\) | 0 |
| Remove \(s\); scan \(s:[a,b]\) | \([a,b]\) | \(a,b\) | 2 |
| Remove \(a\); scan \(a:[c]\) | \([b,c]\) | \(c\) | 1 |
| Remove \(b\); scan \(b:[c]\) | \([c]\) | None; \(c\) is discovered | 1 |
| Remove \(c\); scan \(c:[a]\) | \([]\) | None; \(a\) is discovered | 1 |
Initialization writes six vertices’ entries. There are \(n_R=4\) removals and \(m_R=2+1+1+1=5\) scanned list entries, so the search uses work proportional to \(6+4+5=15\) counted units, up to the constant cost assigned to each operation. The arcs \(de\) are not scanned because \(d\) is not reached. The total edge count is \(m=6\), which is larger than \(m_R=5\).
Check: The reached set is \(\{s,a,b,c\}\): the queue discovers \(a,b\) from \(s\), then \(c\) from \(a\), and no scanned arc reaches \(d\) or \(e\). The scanned-list total is \(2+1+1+1=5\), matching the arcs \(sa,sb,ac,bc,ca\) whose tails are reached.
Worked Example: Adjacency Matrix Row Scans
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,14,23,35,42\}\). The rows of the adjacency matrix, in vertex order \(1,2,3,4,5\), are \(01010\), \(00100\), \(00001\), \(01000\), and \(00000\). Start BFS at \(1\).
| Action | Queue after action | Newly discovered | Matrix entries tested |
|---|---|---|---|
| Initialize; enqueue \(1\) | \([1]\) | \(1\) | 0 |
| Remove \(1\); scan row \(1\) | \([2,4]\) | \(2,4\) | 5 |
| Remove \(2\); scan row \(2\) | \([4,3]\) | \(3\) | 5 |
| Remove \(4\); scan row \(4\) | \([3]\) | None; \(2\) is discovered | 5 |
| Remove \(3\); scan row \(3\) | \([5]\) | \(5\) | 5 |
| Remove \(5\); scan row \(5\) | \([]\) | None | 5 |
All five vertices are reached, so \(n_R=5\). The row scans test \(5\cdot5=25\) entries, although only five matrix entries contain \(1\). BFS gives distances \(d(1,1)=0\), \(d(1,2)=d(1,4)=1\), \(d(1,3)=2\), and \(d(1,5)=3\).
Check: The five \(1\)-entries in the displayed rows occur at positions \(12,14,23,35,42\), exactly the five arcs in \(E\). The matrix search still tests all \(25\) entries because it scans five complete rows.
Worked Example: Comparing Both Representations
Let \(V=\{p,q,r,x,y\}\) and \(E=\{pq,qr,xy\}\), and start at \(p\). The adjacency lists are \(p:[q]\), \(q:[r]\), \(r:[]\), \(x:[y]\), \(y:[]\). For the matrix, the rows in the order \(p,q,r,x,y\) are \(01000\), \(00100\), \(00000\), \(00001\), and \(00000\).
| Queue action | Queue after action | List entries scanned | Matrix entries tested |
|---|---|---|---|
| Enqueue \(p\) | \([p]\) | 0 | 0 |
| Remove \(p\) | \([q]\) | 1 | 5 |
| Remove \(q\) | \([r]\) | 1 | 5 |
| Remove \(r\) | \([]\) | 0 | 5 |
Here \(R=\{p,q,r\}\), so \(n_R=3\) and \(m_R=2\). The list scans \(1+1+0=2\) entries; the matrix scans \(3\cdot5=15\) entries. Both implementations also initialize arrays for \(n=5\) vertices. The arcs \(xy\) are present in the graph but are not examined by this single-source search.
Check: The list scan count agrees with the two arcs leaving reached vertices, \(pq\) and \(qr\). The matrix scan count is three rows, each with five entries, giving \(15\). In both representations the queue empties after \(p,q,r\) have been processed.
Space, Initialization, and a Common Mistake
Runtime bounds should be kept separate from space bounds. An adjacency-list representation stores a list for every vertex and one list entry per arc, so its storage is \(\Theta(n+m)\). An adjacency matrix stores \(n^2\) entries, so its storage is \(\Theta(n^2)\). These are graph-representation costs, not extra BFS workspace.
BFS typically keeps a state, distance and parent entry for each vertex, as well as a queue. These arrays and the queue require \(\Theta(n)\) auxiliary space in the usual implementation. Thus the total space, including the input representation, is \(\Theta(n+m)\) for lists and \(\Theta(n^2)\) for a matrix; the extra space used by BFS itself is \(\Theta(n)\) in either case. If a program stores only some of these arrays, its constants or exact arrays may differ, but the stated asymptotic bounds remain the usual ones.
Common mistake: saying adjacency-list BFS takes \(O(m)\) time. Take \(V=\{1,\ldots,1000\}\), \(E=\varnothing\), and source \(1\). Then \(m=0\), but initializing the search state for all \(1000\) vertices takes \(\Theta(1000)\) operations. BFS then removes \(1\) and scans its empty list. The correct bound including initialization is \(O(n+m)=O(1000+0)\), not \(O(m)=O(0)\). The vertex term is essential, particularly for sparse graphs and graphs with isolated vertices.
The representation also matters when counting initialization. Initializing BFS arrays takes \(\Theta(n)\) time for either representation. Initializing an adjacency matrix from scratch is a separate \(\Theta(n^2)\) task, while initializing empty lists and inserting arcs takes \(\Theta(n+m)\). State explicitly whether the input representation is already available before comparing search runtimes.
Check Your Understanding
For each question, count array initialization separately from neighbor scanning.
- A directed graph has \(n=8\) vertices. From a source, BFS reaches \(n_R=3\) vertices, and the outgoing lists of those vertices contain \(m_R=4\) arcs. What is the adjacency-list running-time bound for this search?
- For the same \(n\) and \(n_R\), how many matrix entries are tested when BFS scans one full row for each reached vertex?
- Explain why an adjacency-list BFS can take \(\Theta(n)\) time when \(m=0\).
- For a graph with \(n=6\), \(m=7\), and every vertex reachable from the source, state the standard search bounds for adjacency lists and for an adjacency matrix.
- Separate the graph-storage space from the auxiliary BFS space for each of the two representations.