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

Question

谁能详细解释一下为什么以及如何在无向图中检测循环的 DFS 上限为 O(|V|)？

Answer 1

无圈图最多有|V| - 1 条边(这是一片森林)。因此，如果 DFS 发现 |V|边缘或更多然后它已经找到一个循环并终止。运行时间因此受到 O(|V|) 的限制。