我知道这个特定问题的答案是 O(V + E)，对于像树这样的图形，这是有道理的，因为每个顶点只被探索一次。
但是，假设图中有一个循环。
例如，让我们使用一个有四个顶点 ABCD 的无向图。
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 成正比。
有任何想法吗？
如果您不维护一个用于避免重新访问已访问节点的visited集合，则 DFS 不是。事实上，它不是完整的算法——因此，如果有路径，它甚至可能找不到路径，因为它会陷入无限循环。O(V+E)
请注意，对于无限图，如果您正在寻找从s到的路径t，即使维护访问集，也不能保证完成，因为您可能会陷入无限分支。
如果您有兴趣保持 DFS 的高效空间消耗优势，同时仍然是完整的 - 您可以使用迭代深化 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)
很容易看出，当且仅当它还没有被访问时，您才在顶点上调用递归，因此答案在顶点和边的数量上确实是线性的。
您可以访问图形的每个顶点和边一定次数，并且仍然是 O(V+E)。另一种看待它的方式是，成本计入边缘，而不是顶点。