AlgoScope

DFS Recursive

The natural recursive form. Each call frame is one vertex, and the current path is the call stack.

Graph traversal, algorithm, beginner
Enter 0, depth 1.0123456u
Enter 0, depth 1.0123456u

DFS Checks: Recursive DFS and its call stack

Decision, step 2 of 15

Call dfs(0): mark it seen, visit number 1. Neighbours 1, 2. 1 is unseen, so the call dives into it before looking at the rest.

Cost

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

A variant of

Taught by the same lesson

DFS Checks covers these too, in the same run.