So hopefully this is a simple question, but I can't seem to find the answer.
The time complexity of DFS is allegedly O(|V|+|E|). Now I'm having issues seeing why it depends on the number of edges. The usual explanation I've seen goes as follows:
Say we implement a DFS using an explicit stack (for simplicity). Say we have a graph where each node is connected to all the rest. We start at some node, visit it and then push all it's neighbors onto the stack. Now we pop the next node and put all of it's neighbors onto the stack. We repeat until we visit all the nodes.
Let's pretend that the node that finds itself on top of the stack is not visited yet in each iteration (best case scenario for this graph). In this case we visited all the nodes in |V| moves, but for each of them we pushed |V|-1 nodes on the stack which means that all the edges are pushed on the stack and the complexity is O(|E|)
A few notes. I'm arguing that the complexity is LESS than that so this proof that only looks at the best scenario for a worst case graph is fine. I'm also assuming that |E| is always larger than |V|. In fact, I'm assuming it's O(|V|^2). This means that O(|V|+|E|) and O(|E|) mean the same thing to me.
Ok, now here's my deal. What if we don't use an explicit stack?
The explosion here is due to the fact that we keep stacking up useless nodes that will never be processed. What if we instead just recurse? The advantage is that we can check if we're done before each recursive call.
Since there's no explicit stack and I'm still only visiting nodes I haven't seen before, I don't see how I can exceed the complexity of O(|V|).
