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

Question

5

请问有人能详细解释一下，为什么并且如何使用深度优先搜索（DFS）在无向图中检测一个循环的上限是O（|V|）吗？

- Sazz

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakov Galka · Accepted Answer

没有循环的图最多只有|V|-1条边（称为森林）。因此，如果DFS发现|V|条边或更多，则已经找到了一个循环并终止。运行时间因此受到O(|V|)的限制。