Depth-First Search

graph

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Explores as far as possible along each branch before backtracking.

Time Complexity

Best

\mathrm{O}\left(V + E\right)

Avg

\mathrm{O}\left(V + E\right)

Worst

\mathrm{O}\left(V + E\right)

Space Complexity

Aux

\mathrm{O}\left(V\right)

Stack + visited set — up to V nodes stored

Pseudocode

1procedure DFS(graph, start, end)

2stack.push(start)

3while stack is not empty do

4node = stack.pop()

5for each neighbor of node do

6if not visited then stack.push(neighbor)