Depth First Search
Going deep first.
Depth first search does the opposite of breadth first. It follows one path as far as it can go, and only when it hits a dead end does it back up and try another. Like exploring a maze by always keeping your hand on the wall.

- Follow one path as far as possible
- Back up at dead ends
- Like exploring a maze
DFS with recursion
Recursion makes depth first search very short. Visit a person, mark them as seen, then explore each unseen friend completely, before moving on to the next. The call stack remembers where to come back to. Run it. Notice the order differs from breadth first. We dive from Ana to Ben to Dev, before ever reaching Cara.
from graph import friends
def dfs(person, visited=None):
if visited is None:
visited = []
visited.append(person)
for f in friends[person]:
if f not in visited:
dfs(f, visited)
return visited
print(dfs("Ana"))['Ana', 'Ben', 'Dev', 'Cara', 'Eli', 'Fay']
Also uses graph.py
friends = {
"Ana": ["Ben", "Cara"],
"Ben": ["Ana", "Dev"],
"Cara": ["Ana", "Dev", "Eli"],
"Dev": ["Ben", "Cara", "Fay"],
"Eli": ["Cara"],
"Fay": ["Dev"],
}DFS or BFS?
Both visit everything in O of V plus E. Use breadth first for shortest paths, and for things that are close by. Use depth first when you need to explore every possibility, find any path at all, detect cycles, or work through dependencies. Depth first can also use an explicit stack instead of recursion, for very deep graphs.
| key | value |
|---|---|
| BFS | queue, nearest first |
| DFS | stack or recursion, deep first |
| Shortest path | BFS |
| Cycles, dependencies | DFS |
Summary
Depth first search dives down one path before backing up. It's short with recursion, and great for exploring every possibility. Next, finding the shortest path.
Key takeaways- Go deep first
- Back up at dead ends
- Recursion or a stack