BFS & DFS

Breadth First Searching

• starts at the top most node


• down to the next level moving across the level from left to right


• and then moving to the next level (repeat) until you find the goal

Depth First Searching

• starts at the top most parent node


• dives down taking the left most path at each node until it can go any "deeper" before backtracking

Comparison

1. BFS guarentees a solution


2. BFS guarentees the best solution


3. BFS requires more memory - must remember what each node is at every level


4. DFS requires less memory - only must remember previous node


5. DFS - may be lucky and find a solution


6. DFS - may follow a branch with no solution


7. DFS may get stuck in an infinite loop - so require backtracking and also tracking of the states