🎓 A1Learner
🔍
0 of 47 lessons completed

Depth-First Search in Interviews

Depth-first search is a search that follows one path as far as it goes before it turns back. It goes deep first, then backtracks to try the next branch.

Spot the signal

A problem asks whether a path exists or what every branch holds. The search follows first neighbours down one path.

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
node = "A"
path = [node]
while graph[node]:
    node = graph[node][0]
    path.append(node)
print(path)

The template

Visit a node, then visit each unvisited neighbour the same way. Recursion holds the path for free.

def dfs(graph, node, seen, order):
    seen.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in seen:
            dfs(graph, neighbour, seen, order)
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
order = []
dfs(graph, "A", set(), order)
print(order)

Worked problem: path exists

A stack walks one branch at a time. Finding the target ends the walk early.

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
def has_path(graph, start, target):
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node == target:
            return True
        if node not in seen:
            seen.add(node)
            for neighbour in graph[node]:
                stack.append(neighbour)
    return False
print(has_path(graph, "A", "F"))

Example

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
def count_reachable(graph, node, seen):
    seen.add(node)
    total = 1
    for neighbour in graph[node]:
        if neighbour not in seen:
            total += count_reachable(graph, neighbour, seen)
    return total
print(count_reachable(graph, "A", set()))

Key points

  • Backtrack: return to the last branch point after a path ends.
  • Use depth-first search when a problem asks to explore every branch or check whether a path exists.
  • A stack or recursion holds the current path.
  • Mark a node visited when it is first reached, so cycles cannot loop forever.
  • Depth-first search finishes one branch before it starts the next.
  • Unlike breadth-first search, it does not finish a level first.

The code counts the start node plus every unvisited neighbour branch. The visited set stops shared nodes from being counted twice. All seven nodes are reachable from A.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What does depth-first search do first?