Skip to main content

BFS VS DFS

· 2 min read

Overview

  • search algorithms for graphs and trees
  • used for unordered graph and tree
  • graph representation
    • adjacent list: space O(V+E)
    • adjacent matrix: space O(V^2)
  • BFS
    • start with root node
    • scan each node in the each level
    • while traversing each level, decide if target is found
  • DFS
    • start with root node
    • follow on branch as far as possible until target is found or hit a leaf node
    • if hit a leaf node, continue search at the nearest ancestor

Comparison

  • memory
    • BFS uses a large amount of memory because need to store pointers to a level(serious problem if the tree is very wide)
    • DFS uses less memory because no need to store all child pointers at a level
  • depend on the data you search for
    • look for people alive in family tree: DFS because targets are likely to be on the bottom of the tree
    • look for people who died: BFS

implementation

BFS: queue

  • recursive
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)

BFS(Q)
}
  • iterative
  procedure BFS(G,v)
initialize a queue Q
Q.push(v)
label v as visited
while Q is not empty
v <- Q.pop()
visit(v)
for all edges from v to w in adjacent(v)
if w is not visited
Q.push(w)
label w as visited

DFS: stack

  • recursive
  procedure DFS(G,v)
label v as visited
for all edges from v to w in adjacent(v)
if w is not visited
DFS(G,w)
  • iterative
   procedure DFS(G,v)
initialize stack S
S.push(v)
while S is not empty
v <- S.pop()
if v is not visited
label v as visited
for all edges from v to w in adjacent(v)
S.push(w)

Solution

  • BFS: complete algorithm, give optimal solution
  • DFS: suboptimal solution

Complexity

  • BFS: worst time O(V+E), worst space O(V)
  • DFS: worst time O(v+E), worst space O(V)