graph - 检测图中循环的时间复杂度

Question

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

此处说明了执行此操作的两种方法。我会假设时间复杂度是根据最坏情况提供的。
第一个是 union-find，据说它的时间复杂度为 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)。

Answer 1

该算法基于 DFS，通常为每个顶点维护一个“已访问”布尔变量，其中包含一位信息——该顶点是否已被访问。所以，没有一个顶点可以被访问超过一次。

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

在图由许多连接的组件组成的情况下，从图的所有顶点开始 DFS是必要的——“已访问”布尔变量保证 DFS 不会一次又一次地遍历相同的组件。