The time complexity of both Depth-First Search (DFS) and Breadth-First Search (BFS) is indeed O (V + E), where V is the number of vertices (or nodes) and E is the number of edges in the graph. Here’s why:
DFS:
1. Visiting vertices: In DFS, each vertex is visited once. This takes O(V) time.
2. Exploring edges: For each vertex, we explore its adjacent edges. Since each edge is explored once, this takes O(E) time.
3. Total time complexity: Therefore, the total time complexity of DFS is O(V) + O(E) = O (V + E).
BFS:
1. Visiting vertices: In BFS, each vertex is also visited once. This takes O(V) time.
2. Exploring edges: For each vertex, we explore its adjacent edges. Again, since each edge is explored once, this takes O(E) time.
3. Queue operations: In BFS, we use a queue to keep track of vertices to visit next. Queue operations (enqueue and dequeue) take constant time, so they don’t affect the overall time complexity.
4. Total time complexity: Therefore, the total time complexity of BFS is also O(V) + O(E) = O (V + E).
In summary, both DFS and BFS have a time complexity of O (V + E) because they visit each vertex once and explore each edge once. The specific order in which they visit vertices and edges differs, but the overall time complexity remains the same.