What is the time complexity of depth-first search?

Worst case O(V + E). Space complexity is O(V) stack depth. Memory is proportional to the depth of the current path, not the width.

Depth-first search

easy

Recursive or iterative, with the call stack made visible either way. Turn on component restarting and the same traversal becomes a connected-components scan.

Worst O(V + E)Space O(V) stack depth

Loading the depth-first search engine…

Where to go next

Breadth-first search

easy

Expands in rings, so it finds shortest paths.

Topological sort

medium

Kahn's algorithm, with cycle detection for free.

Rat in a maze

medium

Watch corridors light up and go dark again.