Breadth First Search

• Breadth First Search expands all possible paths simultaneously.
• This is guaranteed to work if there is a solution.
• Marking can reduce the cost.
• BFS is also a simple undirected search.
• How do DFS and BFS trade-off in time?
• How do they trade-off in space?
• Best, average and worst case analysis