AlgoScope

Depth-First Search

Go as deep as possible before backtracking. The recursion stack is the frontier.

Graph traversal, algorithm, beginnerAlso called DFS
Vertex 0 is visited as number 1. 2 neighbours are pushed.0112345u
Vertex 0 is visited as number 1. 2 neighbours are pushed.0112345u

BFS and DFS: Depth-first from 0

Decision, step 2 of 10

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.

How bfs and dfs works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Before this

Variants

  • Recursive DFSImplicit call stack.
  • Iterative DFSExplicit stack. Visiting order differs slightly.

Leads to

Topics that need this one first.

Taught by the same lesson

BFS and DFS covers these too, in the same run.