BFS_VS_DFS

BFS vs DFS

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    BFS(Q)
    {
    if (|Q| > 0)
    v <- Dequeue(Q)
    Traverse(v)
    foreach w in children(v)
    Enqueue(Q, w)
    BFS(Q)
    }
  • iterative

1
2
3
4
5
6
7
8
9
10
11
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
1
2
3
4
5
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
1
2
3
4
5
6
7
8
9
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)