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
12345678910BFS(Q){if (Q > 0)v < Dequeue(Q)Traverse(v)foreach w in children(v)Enqueue(Q, w)BFS(Q)}iterative


DFS: stack
 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)