Suppose a graph G has n vertices and e edges using the BFS algorithm : Which…
2025
Suppose a graph G has n vertices and e edges using the BFS algorithm :
Which of the following statements is correct regarding the time complexity of BFS with different graph representations ?
- A.
BFS runs in O(e^2) time using an adjacency list and O(n^2) time using an adjacency matrix
- B.
BFS runs in O(e) time using an adjacency list and O(n^2) time using an adjacency matrix
- C.
BFS runs in O(n) time regardless of the graph representation
- D.
BFS runs in O(n.e) time using both adjacency list and matrix
Attempted by 89 students.
Show answer & explanation
Correct answer: B
The time complexity of BFS depends on how the graph is stored:
Adjacency List: To perform BFS, we visit every vertex once and for each vertex, we iterate through its adjacency list to find neighbors. The total number of iterations across all vertices is equal to the number of edges. Thus, the complexity is O(n + e). In many contexts, this is simplified to O(e) if the graph is connected.
Adjacency Matrix: To find the neighbors of a single vertex, we must scan an entire row of length $n$. Since we do this for all n vertices, the total time complexity is O(n X n), which is O(n^2).