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|) ?

Sazz
  • 57
  • 6

1 Answers1

8

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 already found a cycle and terminates. The runtime is accordingly bounded by O(|V|).

Yakov Galka
  • 66,221
  • 15
  • 132
  • 206
  • 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..." – Paul Hankin Apr 21 '19 at 08:47
  • @PaulHankin: Thanks, I didn't pay attention for the constants (the question is about asymptotic). :) – Yakov Galka Apr 21 '19 at 08:51