Depth First Search (DFS) is a crucial algorithm in graph theory that can be implemented in two ways: iterative and recursive. In this article, we’ll focus on the recursive approach as it’s easier to understand and code. If you’re new to recursion, this is a fantastic opportunity to grasp its concept. We’ll be implementing DFS in pure Python.

Let’s dive into the code for the DFS algorithm:

The DFS function takes three inputs: a set of visited nodes (initially empty), a graph definition, and a starting node. The logic is straightforward:

1. Check if the node has been visited before

a. If yes, skip checking its neighbors

b. If no, print the node and visit its neighbors using a loop

2. Repeat the process until all nodes are visited

The function returns None as it prints visited nodes and updates the external set. To modify the behavior to return a set of visited nodes without printing, you can make a small adjustment to the input.

Example 1

Let’s create an exemplary graph using an adjacency matrix as a Python dictionary. The graph will be directed for clarity, but DFS works well for undirected graphs too.

After running the function call command, the output will be a list of visited nodes.

Alternatively, you can use a modified version of the code that doesn’t rely on global variables. By passing an empty set directly, you can get the same output.

Visualize how the function stack and final set are built step-by-step with the animation below.

Example 2

Let’s build and traverse a decision tree in this example. The graph definition is provided:

After running DFS on this graph, you’ll get the output:

Observe how DFS traverses the tree with the animation below:

Summary

DFS is a powerful algorithm that plays a vital role in traversing graphs efficiently. By understanding its recursive nature and exploring examples in this article, you can lay a strong foundation for mastering other traversal algorithms like Breadth First Search (BFS) and path-finding algorithms such as Dijkstra’s or A*.

Experiment with different graphs and data structures to see how DFS behaves. In future articles, we’ll delve into BFS and explore their use cases and limitations.

Keep honing your skills and exploring these graph algorithms. Happy coding!

References

[1] Tsok, Samuel & Yakubu, Hosea & Solomon, Rwat. (2023). Graph Models of Social Media Network As Applied to Facebook and Facebook Messenger Groups. International Journal on Computer Science and Engineering. Vol. 9. Pg 1. [link]

[2] Tianlun Dai, Wenchao Zheng, Jiayue Sun, Cun Ji, Tao Zhou, Mingtong Li, Wei Hu, Ziqiang Yu, Continuous Route Planning over a Dynamic Graph in Real-Time, Procedia Computer Science, Volume 174, 2020 [link]