Depth-First Search (DFS)¶
Explore one path deeply before backtracking, so you can trace structure, follow branches, and reason about stack-like traversal behavior.
DFS is the natural contrast to BFS. Instead of expanding outward one layer at a time, it commits to a path, goes as far as it can, and only then backs up to try another branch.
graph = {
"A": ["B", "C", "D"],
"B": ["E", "F"],
"C": ["G"],
"D": ["H"],
"E": [],
"F": [],
"G": [],
"H": [],
}
visited = []
def dfs(node):
if node in visited:
return
visited.append(node)
for neighbor in graph[node]:
dfs(neighbor)
dfs("A")
print("DFS visit order:", visited)DFS visit order: ['A', 'B', 'E', 'F', 'C', 'G', 'D', 'H']
DFS follows a branch deeply, then backs up when it hits the end¶
BFS taught level-by-level exploration with a queue. DFS changes the rhythm completely: follow one path as far as possible, backtrack when no new neighbor remains, and continue from the most recent unfinished branch.
Core Explanation¶
DFS follows a branch deeply before returning. It is often used in traversal, path finding, recursion practice, cycle reasoning, and situations where exploring one complete possibility before trying the next is useful.
Read the figure without code
the node labels show one valid DFS order
the red branch shows the first deep dive from
AthroughBto its childrenDFS does not visit
CorDuntil it has finished the unfinished work underBthe later blue nodes appear only after backtracking has returned to the start area
Because neighbor order can change, DFS can have multiple valid visit orders on the same graph.
Think of walking through a maze by choosing one corridor and continuing until you must turn back.
BFS would inspect all nearby corridors first. DFS is willing to go deep before it knows what sits beside the start node.
DFS is common in graph traversal, recursive structure processing, topological reasoning, and path exploration.
Continuity from BFS
BFS emphasized queues and frontier expansion by level. DFS emphasizes stack behavior, recursion, and backtracking. The graph structure is the same; only the exploration strategy changes.
Worked Example and Practice Lab¶
Iterative DFS with an explicit stack¶
Expected output
Iterative DFS order: ['A', 'B', 'E', 'F', 'C', 'G', 'D', 'H']This version makes the LIFO stack behavior explicit: the most recently discovered unfinished branch is the next one explored.
Recursive DFS¶
Expected output
Recursive DFS order: ['A', 'B', 'E', 'F', 'C', 'G', 'D', 'H']Recursive trace: entering, base case, and closing stack frames¶
What to notice
each recursive call goes one layer deeper into the call stack
the base case appears when there is no new neighbor left to explore
the closing messages appear while the stack unwinds back toward the starting node
Exercises¶
Explain why DFS is more naturally associated with a stack than a queue.
Describe what backtracking means in your own words.
Give one reason a DFS visit order can differ from BFS on the same graph.
Name one situation where exploring deeply before returning could be useful.
Hint
Focus on which node gets processed next: the oldest discovered node or the most recently discovered unfinished node.
Guided Practice¶
What structure most naturally supports depth-first search?¶
Why can DFS have more than one valid visit order on the same graph?¶
Key Takeaway¶
DFS follows one path deeply before backtracking, which makes it a strong contrast to BFS and a useful stepping stone toward later graph reasoning. The next notebook, Dijkstra’s algorithm, shifts again: not just exploring a graph, but choosing the cheapest path when edges carry weights.