# 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

10BFS(Q)

{

if (|Q| > 0)

v <- Dequeue(Q)

Traverse(v)

foreach w in children(v)

Enqueue(Q, w)

BFS(Q)

} - iterative

1 | procedure BFS(G,v) |

### DFS: stack

- recursive

1 | procedure DFS(G,v) |

- iterative

1 | procedure DFS(G,v) |

## 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)