The time complexity of the Depth-First Search (DFS) algorithm is $$O(V + E)$$, where $$V$$ is the number of vertices and $$E$$ is the number of edges in the graph. This complexity can be understood by analyzing the operations performed by the DFS algorithm:
Vertex Exploration: Each vertex in the graph is visited exactly once. When a vertex is visited, it is marked as visited to ensure it is not revisited. This contributes $$O(V)$$ to the time complexity because there are $$V$$ vertices, and each vertex is processed once.
Edge Exploration: For each vertex, the algorithm explores all its adjacent edges. Since each edge connects two vertices, and each edge is considered exactly once during the traversal, this contributes $$O(E)$$ to the time complexity. The sum of the sizes of the adjacency lists of all the vertices is $$E$$, meaning each edge is checked once.
Combining these two parts, the total time complexity of DFS is $$O(V + E)$$ because the algorithm processes each vertex and each edge exactly once in the worst case[1][4][16].
Detailed Explanation
Initialization: The algorithm initializes data structures such as the visited array, which takes $$O(V)$$ time.
Recursive Calls: In the recursive implementation of DFS, each vertex is visited once, and for each vertex, all its adjacent vertices (edges) are explored. This results in a total of $$O(V)$$ vertex visits and $$O(E)$$ edge explorations.
Stack Operations: In the iterative implementation using a stack, each vertex is pushed and popped from the stack once, and each edge is considered once, leading to the same $$O(V + E)$$ complexity.
Example
Consider a graph with $$V$$ vertices and $$E$$ edges. The DFS algorithm will:
Start at a vertex, mark it as visited, and push it onto the stack (or call the recursive function).
For the current vertex, explore each adjacent vertex (edge) that has not been visited.
