# Carl's Bonfire

Failure to Failure Without Losing Passion

0%

# 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

• scan each node in the each level
• while traversing each level, decide if target is found
• DFS

• 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

• recursive
• iterative

• recursive
• iterative

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