0

I'm new to DFS and just learned that the time complexity of DFS will be O(V+E) if using an adjacency list. I was wondering what the time complexity of DFS would be if back edges were included, as back edges require the search to backtrack to previously discovered nodes.

I tried searching this up online but I can't seem to find a good answer for this.

Edward
  • 1
  • 1
  • Which sources did you find which said it is only O(V+E) when there are no back-edges? – kaya3 May 26 '21 at 19:34
  • https://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e i assumed that it applies to DFS in general, but I was wondering what the time complexity would be if back edges were included – Edward May 27 '21 at 03:15
  • The second answer to that question explicitly mentions back-edges: https://stackoverflow.com/a/11468703/12299000 Back-edges are expected as a normal part of the DFS algorithm, any discussion of its complexity should involve the case where there are back-edges. – kaya3 May 27 '21 at 06:00

0 Answers0