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

Question

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

Answer 1

一个没有环的图最多有|V| - 1 条边（这是一片森林）。因此，如果 DFS 发现 |V| 边缘或更多然后它已经找到一个循环并终止。运行时间相应地以 O(|V|) 为界。