Loading...
Depth-First Search dives down one path until it hits a dead end, then backtracks and tries the next branch — naturally expressed with recursion (an implicit stack). It powers cycle detection, topological sorting, connected-component labeling, and maze/puzzle solving. Runs in O(V + E).
Explores as far as possible down each branch before backtracking.
Start the search at A.
| Average case | O(V + E) |
| Worst case | O(V + E) |
| Space | O(V) |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def dfs(adj, start):
visited = [False] * len(adj)
order = []
def visit(u):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
visit(v)
visit(start)
return orderRunning Depth-First Search (DFS) on the sample graph, step by step:
The control flow of the algorithm as a diagram: