Space 图中 DFS 和 BFS 的复杂度

Question

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

通过使用邻接表 space，在一般情况下会降低复杂性，即 < v^2。但在最坏的情况下，它会是 O(v^2)。即使包括 Queue，也是 O(n^2)（忽略较低的值）

但是，DFS 的场景是什么？即使我们使用邻接matrix/list。 Space 复杂度为 O(v^2)。但这似乎是一个非常宽松的界限，在不考虑堆栈框架的情况下也是如此。

关于复杂性，我是否正确？如果不是，BFS/DFS 的 space 复杂度是多少？在计算 DFS 的 Space 复杂度时，我们是否考虑堆栈框架？

图的 BFS 和 DFS 的 space 复杂度的紧界是什么

Answer 1

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

伪代码1 输入：一个图 Graph 和 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的space复杂度可以表示为O(|V|)，其中|V|是顶点集的基数。在最坏的情况下，您需要将所有顶点保留在队列中。

DFS 的 space 复杂性取决于实现。具有最坏情况 space 复杂度 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）

广度优先搜索完成，深度优先搜索未完成。

Space 图中 DFS 和 BFS 的复杂度

Space Complexity of DFS and BFS in graph

depth-first-search

breadth-first-search

space-complexity