Backtracking
- Algorithms course
- Intermediate
- Lesson 59/80
- 4 min
Backtrack at dead ends and try a new branch.
Backtracking in action
When DFS hits a dead end, it steps back and tries a new branch from the previous level.
In stack-based DFS, backtracking happens naturally via stack pops; no extra code needed.
So DFS systematically walks all branches even on deep graphs; no branch is skipped.
Completing the path
During backtracking the visited set ensures each vertex is processed once; this yields efficient path discovery.
This makes DFS safe even on cyclic graphs; no infinite loop arises.
The visited set prevents repeats during backtracking and ensures correct path completion.
Practice DFS depth
Write dfs_depth(graph, start). Run stack-based DFS and return the maximum depth reached. Print 3 with print(dfs_depth({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).
Starter code
def dfs_depth(graph, start):
# Find maximum depthSample solution
def dfs_depth(graph, start):
# Find maximum depth
visited = set()
stack = [(start, 0)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node not in visited:
visited.add(node)
if depth > max_depth:
max_depth = depth
for nb in graph[node]:
if nb not in visited:
stack.append((nb, depth + 1))
return max_depth
print(dfs_depth({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Backtracking: match the terms
| Term | Meaning |
|---|---|
backtrack |
Return |
dead end |
Dead end |
pop |
Take back |
visited |
No repeat |
2 How does backtracking happen in stack DFS?
- Via stack pop Correct answer
- Via queue pop
- By pulling from heap
- With a hash
Explanation: Via stack pop.
3 Pop back
node = stack.____node = stack.pop()Explanation: pop() is right.