Depth-First Search

Plunges as deep as possible along each branch before backtracking, using a stack (here, the call stack). Great for connectivity, cycle detection and topological order — but the path it finds is not necessarily the shortest.

Best

O(V+E)

Average

O(V+E)

Worst

O(V+E)

Space

O(V)