algorithm - 机器人矩阵和邻接表的 BFS 和 DFS 的时间复杂度

Question

在此处输入图像描述

在此处输入图像描述

以上是 BFS 和 DFS 的伪代码。

现在通过我的计算，我认为这两个代码的时间复杂度都是 O(n)，但我还有另一个困惑，它可能是 O(V+E)，其中 V 代表顶点，E 代表边。谁能给我两个伪代码的详细时间复杂度。

简而言之，矩阵和邻接表上 BFS 和 DFS 的时间复杂度是多少。

标签： algorithmcomplexity-theorydepth-first-searchbreadth-first-search

Answer 1

让我们首先分析 BFS 对于邻接表实现的时间复杂度。对于广度优先搜索，这就是我们所做的：从一个节点开始并将其标记为已访问。然后将该节点的所有邻居标记为已访问并将它们添加到队列中。然后从队列中取出下一个节点并执行相同的操作，直到队列为空。如果队列为空但仍有未访问的节点，则为该节点再次调用 BFS 函数。当我们在一个节点上时，我们检查该节点的每个邻居以填满队列。如果邻居已经被访问过 (visited[int(neighbor) - 1] = 1)，我们不会将其添加到队列中。节点的邻居是通过边连接到它的另一个节点，因此检查所有邻居意味着检查所有边。这使得我们的时间复杂度为 O(E)。此外，由于我们将每个节点都添加到队列中（稍后将其弹出），它使时间复杂度 O(V)。那么我们应该拿哪一个呢？

好吧，我们应该取 E 和 V 的最大值。这就是我们说 O(V+E) 的原因。如果其中一个大于另一个，则较小可以看作是一个常数。

例如，如果我们有一个有 N 个节点的连通图，我们将有 N*(N-1) 条边。在每个节点上，我们将检查所有邻居，这会进行 N*(N-1) 次检查。因此时间复杂度将是 max(N, N*(N-1)) = N*(N-1) = O(N^2)

例如，如果我们有一个有 N 个节点的稀疏图，并且说 sqrt(N) 很多边，我们不得不说 BFS 的时间复杂度应该是 O(N)。

相同的逻辑可以应用于 DFS。您访问每个节点并检查每个边以深入了解图形的深度。它再次使它成为 O(V+E)。

至于你的假设，它是部分正确的。然而，正如我上面解释的，我们不能说时间复杂度总是 O(N)。（我假设 N 是顶点数，您没有在问题中指定。）

请注意，这些是用于邻接列表实现的。对于邻接矩阵实现，要检查节点的邻居，我们必须检查与相关行对应的所有列，这使得 O(V)。我们必须对所有顶点都这样做，因此它是 O(V^2)。

因此，对于矩阵实现，时间复杂度不依赖于边数。然而在大多数情况下 O(V+E) << O(V^2)，因此更喜欢邻接表实现。