Analysis of Breadth-First Search (BFS)
Analysis of Breadth-First Search (BFS)
When the graph is represented using adjacency lists, the running time of BFS is:
Θ(V+E)where:
- V = number of vertices
- E = number of edges
The CLRS analysis uses aggregate analysis. The important idea is that although BFS contains nested loops, it does not take O(VE) time. Each vertex and each edge is processed only a limited number of times.
1. The BFS Algorithm
Recall the main part of BFS:
BFS(G, s) for each vertex u ≠ s u.color = WHITE u.d = ∞ u.π = NIL s.color = GRAY s.d = 0 s.π = NIL Q = empty queue ENQUEUE(Q, s) while Q ≠ empty u = DEQUEUE(Q) for each vertex v in Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.π = u ENQUEUE(Q, v) u.color = BLACK
We will analyze each part separately.
2. Analysis of Initialization
The first loop is:
for each vertex u ∈ V
It initializes every vertex.
For each vertex, we perform a constant number of operations:
u.color = WHITE u.d = ∞ u.π = NIL
There are V vertices.
Therefore:
O(V)time.
The initialization of the source vertex and queue also takes constant time.
So the total initialization cost is:
O(V)3. How Many Times Is a Vertex Enqueued?
This is a very important part of the CLRS analysis.
A vertex starts as:
WHITE
When BFS discovers it for the first time:
WHITE → GRAY
and immediately executes:
ENQUEUE(Q,v)
After becoming GRAY, it never becomes WHITE again.
Therefore, the condition:
if v.color == WHITE
can be true at most once for each vertex.
Hence:
Each vertex is enqueued at most onceSince there are V vertices:
Total ENQUEUE operations≤V4. How Many Times Is a Vertex Dequeued?
Every vertex that is enqueued is eventually dequeued.
Since each vertex is enqueued at most once:
Each vertex is dequeued at most onceTherefore:
Total DEQUEUE operations≤V5. Cost of Queue Operations
In a standard FIFO queue:
ENQUEUE DEQUEUE
each takes:
O(1)time.
There are at most V enqueue operations and V dequeue operations.
Therefore:
So the total cost of all queue operations is:
O(V)6. The Most Important Part: Scanning Adjacency Lists
Now consider:
for each vertex v in G.Adj[u]
This is where students often incorrectly conclude that BFS takes O(VE).
It does not.
Why?
Because the adjacency list of a vertex is scanned only when that vertex is dequeued.
And each vertex is dequeued at most once.
Therefore:
Each adjacency list is scanned at most once.
7. Example
Suppose:
Adj[A] = B → C → D Adj[B] = A → E Adj[C] = A → F Adj[D] = A Adj[E] = B Adj[F] = C
When BFS dequeues A:
Adj[A]
is scanned once.
When BFS dequeues B:
Adj[B]
is scanned once.
Similarly:
Adj[C] Adj[D] Adj[E] Adj[F]
are each scanned once.
We never repeatedly scan Adj[A].
8. How Many Adjacency-List Entries Are There?
This is the key observation from CLRS.
For a directed graph:
because each directed edge appears once.
Therefore, the total number of adjacency-list entries scanned is:
EUndirected Graph
For an undirected graph, an edge:
(u,v)appears twice:
v in Adj[u]
and
u in Adj[v]
Therefore:
Since the constant 2 does not matter in asymptotic notation:
Therefore, even for an undirected graph, the total adjacency-list scanning cost is:
O(E)9. Total Cost of Scanning Adjacency Lists
Since every adjacency list is scanned at most once:
u∈V ∑∣Adj[u]∣For a directed graph:
For an undirected graph:
Thus in either case:
O(E)10. Why Isn't the Nested Loop O(VE)?
This is perhaps the most important point to emphasize to students.
The code looks like:
while Q ≠ empty u = DEQUEUE(Q) for each v in Adj[u]
Students may think:
V iterations × E iterations = O(VE)
But that is incorrect.
The inner loop does not run E times for every vertex.
Instead, the inner loop runs:
∣Adj[u]∣times for each specific vertex u.
Therefore the total is:
which is:
Efor a directed graph and 2E for an undirected graph.
Hence:
O(E)11. Putting Everything Together
We have three major costs.
Initialization
O(V)Queue operations
O(V)Scanning adjacency lists
O(E)Therefore:
which simplifies to:
O(V+E)12. Why CLRS Says "Linear in the Size of the Adjacency-List Representation"
The adjacency-list representation itself occupies:
space.
BFS takes:
time.
Therefore CLRS says:
BFS runs in time linear in the size of the adjacency-list representation of G.
In other words:
Size of graph representation ↓ V + E ↓ BFS running time ↓ Θ(V + E)
13. Aggregate Analysis Perspective
CLRS specifically uses aggregate analysis.
Instead of asking:
What is the cost of each individual operation?
we ask:
What is the total cost of all operations performed during the entire BFS?
For example:
| Operation | Maximum number of times | Cost each | Total |
|---|---|---|---|
| Initialize vertex | V | O(1) | O(V) |
| ENQUEUE | V | O(1) | O(V) |
| DEQUEUE | V | O(1) | O(V) |
| Examine adjacency-list entries | E (or 2E) | O(1) | O(E) |
| Total | O(V + E) |
This is why the analysis is called aggregate analysis.
14. Space Complexity
It is also useful to distinguish running time from space.
The adjacency-list representation requires:
space.
BFS additionally maintains:
- color for every vertex
- distance for every vertex
- parent for every vertex
- queue
These require:
O(V)additional space.
Therefore the auxiliary space used by BFS, excluding the input graph representation, is:
O(V)If the graph representation is included, total space is:
Θ(V+E)15. What Happens with an Adjacency Matrix?
The result assumes an adjacency-list representation.
If we use an adjacency matrix, then for every dequeued vertex u, we have to examine an entire row of V entries to find its neighbors.
Since there can be V vertices:
entries may be examined.
Therefore BFS using an adjacency matrix takes:
O(V^2)time.
So:
| Representation | BFS Time |
|---|---|
| Adjacency List | Θ(V + E) |
| Adjacency Matrix | Θ(V²) |
16. The Key Reason BFS Is Efficient
The most important observation in the analysis is:
Each vertex is discovered, enqueued, and dequeued at most once, and each adjacency list is scanned at most once.
Therefore:
Total work=O(V)+O(E)=O(V+E)
Comments
Post a Comment