DFS和BFS在图中的空间复杂度

Question

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

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

但是，DFS的情况如何？即使我们使用邻接矩阵/列表。空间复杂度将为O（v ^ 2）。但这似乎是一个非常宽松的界限，也无需考虑堆栈框架。

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

对于图的BFS和DFS，空间复杂度的严格界限是什么

Answer 1

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

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

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

  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（| V |），其中| V |是一组顶点的基数。这是因为在最坏的情况下，您需要将所有顶点保持在队列中。

DFS的空间复杂度取决于实现，如下所示是具有最坏情况空间复杂度O（| E |）的DFS的非递归实现，其中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）

宽度优先搜索已完成，而深度优先搜索未完成。