图中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也是。

伪码1输入:图图和图的起始顶点根

输出:目标状态。父链接将最短路径追溯到根。

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

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

DFS的空间复杂度取决于实现。在DFS的非递归实现中，最坏的空间复杂度为O({##**$}})如下，其中E是边集的基数：

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

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