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

Question

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

标签： algorithmgraphdepth-first-search

Answer 1

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