graph - 深度优先搜索的运行时间

Question

我对 DFS 的运行时间有疑问。我知道它的 O(n + m)，但根据维基百科，还有另一个运行时间：O(b^d)。两者有什么区别，还是表示相同。

这是在维基百科中写的：“O(|E|) 用于不重复遍历的显式图，O(b^d) 用于隐式图”

Answer 1

您在典型算法类中使用的大部分内容都是显式图，但这些可能不是现实世界中常见的表示。

对于这些显式图，深度优先搜索的运行时间为O(V + E)（或 O(n + m)，相同）；在这里，V 代表图中的顶点数，E 代表图中的边数。这在直觉上应该是有道理的，因为深度优先搜索是一种遍历算法，用于以深度优先搜索方式遍历整个图，我们在遍历算法遇到死胡同后回溯。好的，但这是最简单的部分。

您不习惯看到的更奇怪的部分是 DFS 的隐式图形表示。根据目前的维基百科，当谈到搜索算法时，“隐式图可以定义为一组规则，用于定义任何指定顶点的所有邻居。” 这可以在文章的邻域表示部分中看到。隐式图只是简单地隐式定义，可能是无限的或非常大，而显式图是有限的并且是预先给定的。隐式图非常适合搜索到一定深度，这是我将在下一点中讨论的内容。

https://en.wikipedia.org/wiki/Implicit_graph

现在我们对什么是隐式图本身有了一个基本的了解，我们可以谈谈您所看到的 DFS 的运行时间。对于 DFS，当我们说隐式图的运行时间为O(b^d)时，请意识到 DFS 算法本身仍然以几乎相同的方式工作。

这里，“b”代表分支因子，“d”代表深度级别。我们只是希望算法只达到一定的深度。Facebook 寻找共同朋友的方法就是一个很好的例子。如果我们想要我们的直接朋友，深度级别将为 1。如果我们想要朋友的朋友，深度级别将为 2。魔方也可以用作 DFS 遍历的“隐式图”，具体取决于立方体的当前状态和未来可能的移动。国际象棋也是一个很好的例子。

说O(V + E)是隐式图的正确上界，但我们可以更精确地使用O(b^d)界，说明我们基本上只将 DFS 带到了隐式图的某个深度。由于隐式图非常大甚至是无限的，这对于为什么我们不想要纯 O(V + E) 示例应该是有意义的。