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