为什么DFS的时间复杂度检测无向图O（| V |）中的循环而不是O（| V | + | E |）？

Question

任何人都可以向我详细解释为什么以及如何在无向图中检测循环的DFS上限为O（| V |）？

Answer 1

没有循环的图最多具有| V | - 1个边缘（它是森林）。因此，如果DFS发现| V |边缘或更多然后它已经找到一个循环并终止。因此，运行时间由O（| V |）限定。