algorithm - 深度优先搜索的最坏情况时间复杂度

Question

我知道这个特定问题的答案是 O(V + E)，对于像树这样的图，这是有道理的，因为每个顶点只被探索一次。

但是假设图中有一个环。

例如，我们来看一个有四个顶点 A-B-C-D 的无向图。
A连接到B和C，B和C都连接到D。所以总共有四个边。 A->B，A->C，B->D，C->D，反之亦然。

让我们做 DFS(A)。

它将首先探索 B，然后探索 B 的邻居 D 和 D 的邻居 C。之后 C 将没有任何边，因此它将返回 D 和 B，然后返回 A。

然后 A 将遍历它的第二条边并尝试探索 C，因为它已经被探索过，所以它不会做任何事情，DFS 将结束。

但是在这里，顶点“C”被遍历了两次，而不是一次。显然，最坏情况下的时间复杂度可以与 V 成正比。

有什么想法吗？

Answer 1

如果您不维护一个已访问集，您使用它来避免重新访问已经访问过的节点，DFS 不是O (V+E)。事实上，它不是完整的算法 - 因此如果有路径，它甚至可能找不到路径，因为它会陷入无限循环。

请注意，对于无限图，如果您正在寻找从 s 到 t 的路径，即使维护了一个访问集，也不能保证完成，因为您可能会陷入无限分支。

如果您有兴趣保持 DFS 高效空间消耗的优势，同时仍然完整 - 您可以使用 iterative deepening DFS ，但如果您希望发现整个图，而不是到特定节点的路径，它不会轻易解决问题。

编辑:设置了visited的DFS伪代码。

DFS(v,visited):
  for each u such that (v,u) is an edge:
       if (u is not in visited):
            visited.add(u)
            DFS(u,visited)

很容易看出，当且仅当尚未访问顶点时，您才对顶点调用递归，因此答案确实与顶点和边的数量成线性关系。