DSA · Chapter 26 of 40
Depth-First Search
DFS follows one path as deep as possible before backtracking, using recursion or an explicit stack. It runs in O(V + E) and is the base for cycle detection, connected components, topological sorting and backtracking.
DFS does not give shortest paths, but it is often simpler to write and uses less memory on wide graphs.
Recursive vs iterative
Recursion is shorter but risks stack overflow on deep graphs; an explicit stack avoids that.
Cycle detection
In a directed graph, a cycle exists if DFS reaches a vertex that is currently on the recursion stack (grey), not just visited.
Example 1 (python)
def dfs(graph, v, seen=None, order=None):
seen = seen or set()
order = order if order is not None else []
seen.add(v)
order.append(v)
for n in graph[v]:
if n not in seen:
dfs(graph, n, seen, order)
return order
print(dfs(graph, 'A'))Output
['A', 'B', 'D', 'C']DFS goes deep before exploring siblings.
Example 2 (python)
def count_components(graph):
seen, count = set(), 0
for v in graph:
if v not in seen:
count += 1
dfs(graph, v, seen, [])
return count
print(count_components(graph))Output
1Each DFS from an unvisited vertex marks one component.
Key points
- DFS uses recursion or an explicit stack.
- Complexity is O(V + E).
- It finds components and detects cycles.
- It does not guarantee shortest paths.
💡 Note: For directed cycle detection track three states: unvisited, in-progress and done.