Depth-First Search
Go as deep as possible before backtracking. The recursion stack is the frontier.
BFS and DFS: Depth-first from 0
Pop 0: new, so visit it as number 1. Its adjacency list: 1, 2. Push the unvisited ones, 1, 2, so that 1 is on top.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Related
Leads to
Topics that need this one first.
Taught by the same lesson
BFS and DFS covers these too, in the same run.