depth-first search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching a graph or tree, exploring each branch as far as possible before backtracking to the most recent vertex with unexplored neighbors.

The traversal starts at a chosen vertex, or node, and follows one edge after another, going deeper until it reaches a vertex whose neighbors have all been visited. At that point it retreats, or backtracks, to the last vertex that still has an unexplored edge and continues from there.

This last-in, first-out behavior maps onto a stack. An implementation can push and pop that stack explicitly, or let recursion use the call stack for the same effect.

Step through the search below to watch it dive as deep as it can, pushing each new vertex onto the call stack, then pop back off to backtrack once a branch dead-ends:

Because a general graph can contain cycles, DFS records which vertices it has already seen, usually in a visited set, so it never processes one twice or loops forever. A tree has no cycles, so a traversal over one can skip that bookkeeping. Ordering the work around each node yields the preorder, inorder, and postorder binary tree traversals.

On a graph stored as an adjacency list, where each vertex keeps a list of its neighbors, DFS visits every vertex and edge once, giving a time complexity of O(V + E) for V vertices and E edges. The same traversal underpins many classic procedures:

• Topological sorting: ordering the vertices of a directed acyclic graph so that every edge points forward.
• Cycle and connectivity checks: detecting cycles, or grouping vertices into connected and strongly connected components.
• Backtracking search: solving mazes, puzzles, and constraint problems by exploring one candidate path at a time.

Depth-first search contrasts with breadth-first search, which uses a queue to fan out level by level and finds the shortest path in an unweighted graph, a guarantee depth-first search doesn’t provide.

Related Resources

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

• Thinking Recursively in Python (Tutorial)
• Python Stacks, Queues, and Priority Queues in Practice (Tutorial)
• Recursion in Python: An Introduction (Tutorial)
• How to Implement a Python Stack (Tutorial)
• Mazes in Python: Build, Visualize, Store, and Solve (Course)
• Thinking Recursively With Python (Course)
• Thinking Recursively in Python (Quiz)
• Python Stacks, Queues, and Priority Queues in Practice (Quiz)
• Recursion in Python (Course)
• Recursion in Python: An Introduction (Quiz)
• Implementing a Stack in Python (Course)