5

Can anyone explain to me in detail why and how the upper bound of DFS to detect a cycle in an undirected graph be O(|V|) ?

1 Answer 1

9

A graph without cycles has at most |V| - 1 edges (it's a forest). Therefore, if the DFS discovers |V| edges or more, then it has already found a cycle and terminates. The runtime is accordingly bounded by O(|V|).

2
  • Upvoted :) A graph without cycles has at most |V|-1 edges. Maybe that's what you meant, because later you say "if the DFS discovers |V| edges or more..." Apr 21, 2019 at 8:47
  • @PaulHankin: Thanks, I didn't pay attention for the constants (the question is about asymptotic). :) Apr 21, 2019 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.