图中DFS和BFS的空间复杂度

Question

我试图了解图中 DFS 和 BFS 的空间复杂度是多少。据我所知，使用邻接矩阵时 BFS 的空间复杂度是O(v^2)顶点v​​数。

通过使用邻接表，在平均情况下，空间复杂度将会降低< v^2。但在最坏的情况下，情况会是这样O(v^2)。即使包括队列，它也会O(n^2)（忽略较低的值）

但是，DFS 的场景是什么？即使我们使用邻接矩阵/列表。空间复杂度为 O(v^2)。但这似乎是一个非常宽松的界限，也不考虑堆栈帧。

关于复杂性，我的说法正确吗？如果，不是，BFS/DFS 的空间复杂度是多少？在计算DFS的空间复杂度时，我们是否考虑堆栈帧？

图的 BFS 和 DFS 的空间复杂度的紧界是多少

Answer 1

如伪代码1所示，邻接矩阵或邻接表的空间消耗不在BFS算法中。邻接矩阵或邻接表是BFS算法的输入，因此不能包含在空间复杂度的计算中。DFS也是如此。

\n\n

伪代码 1\n输入：图 Graph 和 Graph 的起始顶点根

\n\n

输出：目标状态。父链接追踪回到根的最短路径

\n\n

  procedure BFS(G,start_v):\n      let Q be a queue\n      label start_v as discovered\n      Q.enqueue(start_v)\n      while Q is not empty\n          v = Q.dequeue()\n          if v is the goal:\n              return v\n         for all edges from v to w in G.adjacentEdges(v) do\n             if w is not labeled as discovered:\n                 label w as discovered\n                 w.parent = v\n                 Q.enqueue(w) \n

\n\n

BFS的空间复杂度可以表示为O(|V|)，其中|V| 是顶点集的基数。在最坏的情况下，您需要将所有顶点保存在队列中。

\n\n

DFS 的空间复杂度取决于实现。最坏情况空间复杂度为 O(|E|) 的 DFS 非递归实现如下所示，其中 E 是边集的基数：

\n\n

procedure DFS-iterative(G,v):\n  let S be a stack\n  S.push(v)\n  while S is not empty\n      v = S.pop()\n      if v is not labeled as discovered:\n         label v as discovered\n         for all edges from v to w in G.adjacentEdges(v) do \n              S.push(w\xef\xbc\x89\n

\n\n

广度优先搜索是完整的，而深度优先搜索则不是。

\n