在图中检测环的时间复杂度

Question

我试图理解在图中检测循环的某些有效方法的时间复杂度。

这里解释了两种方法。这里。我认为时间复杂度是以最坏情况为基础提供的。
第一种是并查集，据说具有O(Vlog E)的时间复杂度。
第二种使用基于DFS的方法，据说具有O(V+E)的时间复杂度。如果我没错，这比O(Vlog E)更高效即渐近复杂度更小。此外，基于DFS的方法对于有向和无向图都适用。

我的问题是我不明白如何认为第二种方法可以在O(V+E)时间内运行，因为DFS的时间复杂度是O(V+E)，而且算法会检查已发现节点相邻的节点是否为起始节点。这肯定意味着该算法的运行时间是O(V²)，因为对于每个已发现的节点，最多可能要遍历V-1个相邻节点？显然，不止一个节点需要遍历n-1个相邻节点是不可能的，但从我的理解来看，这仍将是运行时间的上限。

希望有人能理解我为什么这样想，并帮助我理解为什么复杂度是O(V+E)。

- bollock1

Answer 1

这个基于DFS的算法通常为每个顶点维护一个“visited”布尔变量，其中包含一个信息位 - 该顶点是否已被访问。因此，任何顶点都不会被访问超过一次。

如果图是连通的，则从任何顶点开始DFS将立即给您答案。如果图是一棵树，则所有顶点将在单次DFS调用中被访问。如果该图不是一棵树，则单次DFS调用将找到一个循环-在这种情况下，可能并非所有顶点都被访问。在两种情况下，由所有已访问顶点引起的子图将在DFS查找的每个步骤中都是一棵树 - 因此遍历的边的总数将为O(V)。因此，我们可以将循环检测算法的时间复杂度估计从O(V+E)降低到O(V)。

当图由多个连通组件组成时，从所有顶点开始DFS是必要的-“visited”布尔变量可确保DFS不会一遍又一遍地遍历同一组件。

- HEKTO

---

我不明白时间复杂度是如何从V+E降低到V的。DFS引导树显然有V-1条边，但我们仍然需要检查一些在引导树中没有出现的边。 - HappyFace

@HappyFace - 这个问题和我的回答中有两个假设没有明确说明 - 图是无向的，且其表示数据结构是每个顶点的邻接表。如果不是这样，O(V) 的限制将不成立。更多信息请参见：https://mathoverflow.net/questions/61869/is-that-possible-to-find-an-algorithm-with-complexity-of-on-to-find-an-acyclic - HEKTO