Python Algorithms

Depth-First Search (DFS) in Python

Follow one path as deep as it goes before backing up. Write DFS with recursion in a few lines.

Intermediate
2 min read
1 runnable example

What you'll learn

Recursive DFS
The visited set
How DFS order differs from BFS

Run in the Python compiler →

DFS from A

A1st
- B2nd
  - D3rd
- C4th
  - E5th

Visit order: A, B, D, C, E.

Go deep, then back up

Depth-first search follows one branch as far as possible before returning to explore another branch.

Key points

Visit a node, then recursively visit each unvisited neighbour.
The visited set stops cycles from looping forever.
DFS reaches D before C, unlike BFS.
It is useful for paths, cycle detection and topological sorting.

When should you use it?

Practice problem solving and data structures.
Process data when every algorithm step must be explicit.
Prepare for programming exercises, exams, and interviews.

Depth-First Search in Python visualizer

O(V + E)

Use Play or Step to follow each comparison and data movement.

Example code

Run code →

main.py

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}

def depth_first(node, visited=None):
    visited = visited or set()
    visited.add(node)
    order = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            order.extend(depth_first(neighbor, visited))
    return order

print(depth_first("A"))

Get a Run button for this example

Result of running the code

['A', 'B', 'D', 'C', 'E']

Code explanation

The visited set prevents repeated work and cycles. Recursive calls act as the traversal stack. Complexity is O(V + E).

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

Try empty, single-item, and duplicate-value inputs.
Print state after every step to observe the algorithm.
Benchmark 100, 1,000, and 10,000 items, then compare another approach.

Run in the Python compiler →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges