Depth-First Search (DFS) Algorithm With Python

Python implementation of DFS graph search algorithm

Breadth-First Search (BFS) and Depth-First Search (DFS) are two of the most fundamental graph traversal techniques to learn. In a previous article I discussed how we can code the BFS algorithm using Python:

In continuation to that, today I’ll write about how to implement the DFS algorithm in Python. First, we will see the basics of DFS and visualize how the algorithm works. Then we will start coding the algorithm in Python.

DFS Basics

For traversing a graph we can take two approaches. We can go level-by-level or we can go to the depth as far as possible.

DFS takes the second approach. It starts with a root node and explores the graph in-depth as far as possible. After reaching a dead-end, the algorithm starts backtracking and eventually completes the search.

Let’s visualize how DFS works with an example:

Let’s assume ‘A’ is the root/source node and we will start traversing the graph from this node. We will keep going to the maximum depth of a branch/route, then backtrack from there and search in another branch. See the following sketch of DFS traversal:

We can think of it as similar to how we would solve a maze. We take a route and keep going until we hit a dead-end. If we hit a dead-end we come back and go to another route.

We can see a recursive nature in this algorithm, and the Stack data structure can help us with this.

DFS Visualization Using Stack

Stack follows Last-in-First-Out (LIFO) principle. The last element entering the stack will leave the stack first.

DFS uses this characteristic of a stack to search a graph. Let’s see how:

Note that I intentionally put the left neighbors later in the stack. If we put the right neighbors last, we would get A -> C -> G -> F -> B -> E -> D. This is also a valid solution.

Recursive DFS

From the above explanation, we can develop a recursive algorithm for DFS:

DFS(graph, source)
    set source as visited
    
    for each node in graph.adj[source]
        if node is not visited
            DFS(graph, node)

We need to keep track of already visited nodes and recursively traverse the neighbors.

Now it’s time to write the code in Python.

Python Implementation of DFS

Output:

DFS: [‘A’, ‘B’, ‘D’, ‘E’, ‘C’, ‘F’, ‘G’]

Here we are using the adjacency-list representation of the graph. You can learn more about graph representations from this reading:

Conclusion

BFS and DFS are two of the most basic algorithms to learn when studying graphs. In this article, we learned how the DFS algorithm recursively traverses a graph. We also saw the Python implementation of the algorithm.

I hope from this article you get a good understanding of the DFS algorithm and how to code it with Python. Thanks for reading.

Helpful Resources

If you enjoy reading articles like these, consider becoming a Medium member. That gives you unlimited access to all stories on Medium. If you sign up using my referral link below, I’ll earn a small commission from your $5 monthly fees. This way you can support me as a writer.