As when we traverse the undirected connected graph using DFS and mark out only edges which we travel during DFS, we end up with a DFS tree which is basically a tree and traversing a tree requires O(v) complexity where v is the number of vertices, then why it stated that complexity is O(v + e)?
I know it's a noob question but I am confused.
The DFS tree is the tree made of the edges you traversed. You indeed only traverse O(V)
edges. But in order to traverse an edge, you first examine the edge to check if it will lead to a vertex you already encountered. This means you examine more edges than you traverse. Indeed, you examine O(E)
edges. So the total work is O(V+E)
.
Note: Because your graph is connected, you are sure that E > V
. In that case the complexity can be rewritten O(E)
.