Space Complexity of DFS

DFS uses memory for the adjacency list, the visited array, and the recursion call stack. The adjacency list takes $O(V + E)$ space. The visited array takes $O(V)$. The call stack depth equals the longest path you explore before backtracking.

In the worst case (a long chain graph), this is $O(V)$. So total space is $O(V + E)$ for the graph storage plus $O(V)$ for the recursion stack. If you use iterative DFS with an explicit stack, the stack space is still $O(V)$ worst case.