AI Hints
Home›DSA in Python Tutorial›Graph Searches
DSA in Python · Lesson 79 of 132

Depth First Search

Going deep first.

⏱ 2 min read▶ Video at 1:33:30🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Depth First Search
From the video: Depth First Search
  • 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.

dfs.pypython
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"))
Output
['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.

keyvalue
BFSqueue, nearest first
DFSstack or recursion, deep first
Shortest pathBFS
Cycles, dependenciesDFS

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
Next up: Shortest Paths — fewest steps with BFS