Space Complexity of DFS and BFS in graph

Question

I am trying to understand what is the space complexity of DFS and BFS in a graph. I understand that the space complexity of BFS while using adjacency matrix would be O(v^2) where v is the number of vertices.

By using the adjacency list space complexity would be decreased in average case i.e < v^2. But in the worst case, it would be O(v^2). Even including Queue, it would be O(n^2) (neglecting the lower value)

But, what is the scenario with DFS? Even if we use the adjacency matrix/list. Space Complexity would be O(v^2). But that seems to be a very loose bound, that too without considering stack frames.

Am I correct, regarding the complexities? If, not what are the space complexities of BFS/DFS? and while calculating Space Complexity for DFS, do we consider stack frame or not?

what is the tight bound of space complexity, for BFS and DFS for graph

rabbit rabbit · Accepted Answer · 2019-10-17T02:05:09

As shown in Pseudocode 1, the space consumption of the adjacency matrix or adjacency list is not in the BFS algorithm. Adjacency matrix or adjacency list is the input to the BFS algorithm, thus it cannot be included in the calculation of space complexity. So does DFS.

Pseudocode 1 Input: A graph Graph and a starting vertex root of Graph

Output: Goal state. The parent links trace the shortest path back to root

  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)

The space complexity of BFS can be expressed as O(|V|), where |V| is the cardinality of the set of vertices. For in the worst case, you would need to hold all vertices in the queue.

The space complexity of DFS depends on the implementation. A non-recursive implementation of DFS with worst-case space complexity O(|E|) is shown as followed, where E is the cardinality of the set of edges:

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）

Breadth-first search is complete, while depth-first search is not.

Space Complexity of DFS and BFS in graph

1 Answers