According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.
The same is said in this Wikibook page on Uninformed Search.
Now the "infobox" of the Wikipedia article on DFS presents the following for the space complexity of the algorithm:
$O(|V|)$, if entire graph is traversed without repetition, $O($longest path length searched$)$ for implicit graphs without elimination of duplicate nodes
which is more similar to what I thought was the space complexity of DFS, i.e., $O(m)$, where $m$ is the maximum length reached by the algorithm.
Why do I think this is the case?
Well, basically we don't need to store any other nodes than the nodes of the path we're currently looking at, so there's no point of multiplying by $b$ in the analysis provided both by the Wikibook and the notes I'm referred you to.
Moreover, according to this paper on IDA* by Richard Korf, the space complexity of DFS is $O(d)$, where $d$ is considered the "depth cutoff".
So, what's the correct space complexity of DFS?
I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.
DFS is considered to […] of the tree
not every graph traversed depth first is a tree. $\endgroup$ – greybeard Jan 7 '17 at 15:54example where a depth-first traversal on a graph would not result in a tree
without giving it too much thought: parsing. (Wait: what do you mean:result in a tree
? The question is about Searching/traversing a graph.) $\endgroup$ – greybeard Jan 7 '17 at 16:28What do you mean by "not every graph traversed depth first is a tree.
You can traverse a graph depth first that has cycles/nodes with more than one predecessor. $\endgroup$ – greybeard Jan 7 '17 at 16:58depth-first doesn't
according to what/which definition of depth-first search/traversal? $\endgroup$ – greybeard Jan 7 '17 at 18:24