DFS can be implemented in two ways: iterative and recursive. Here, I’ll show you how to do it recursively as IMHO it is easier to understand and to code. This is also a fantastic opportunity to learn how recursion works if you’re not familiar with it yet. DFS implementation will be in pure Python.
Below there is a code for the DFS algorithm itself.
There are three inputs to the function: a set of visited nodes (usually initially empty), a graph definition and a starting node. The logic is simple, yet effective:
1. First, we check if we have visited a given node already
a. If yes, skip checking its neighbors
b. If no, print the node and start visiting its neighbors (the “for loop”)
2. Repeat, till all nodes are in the list of visited nodes
In this case, the function returns None (effectively nothing) because it prints the visited nodes and writes them to the set defined externally. We can change its behavior to return a set of all visited nodes without printing values like that:
Example 1
First, we must define our exemplary graph. For this, we’ll use the adjacency matrix as a Python dictionary. In each key-value pair, a key is a node, and a value is a list of nodes connected to it (neighbors).
Below is the code creating the first exemplary graph in the computer memory. In this case, it is a directed graph (for clarity and simplicity) but DFS works well for undirected ones too.
After running a function call command the output is a series of nodes that were visited:
Or with the alternative version of the code like below. Here we can just make a small change to the input not to use any global variable and pass an empty set directly. Output then is:
Let’s visualize how a functions stack and a final set is being built step-by-step. This is depicted on the animation below.
Example 2
In this example, we will build and traverse a special kind of graph — a decision tree. A definition of the graph is below.
After running the DFS on this graph the output is:
The animation below shows what the graph looks like and how DFS traversed it.
Summary
Depth First Search is an essential algorithm in graph theory, widely used across multiple domains from social networks to decision trees. Its recursive nature makes it easy to understand and implement, as demonstrated by the examples in this article. The simplicity of DFS, along with its ability to efficiently explore all nodes in a graph, makes it a powerful tool for solving various computational problems. Understanding how DFS works lays the groundwork for mastering other algorithms such as Breadth First Search (BFS) and path-finding algorithms like Dijkstra’s or A*.
Try experimenting with larger and more complex graphs, and explore how it behaves with different data structures. In future articles, we will explore other traversal methods like BFS and further investigate their use cases, advantages, and limitations.
Keep practicing and pushing your limits, and soon graph algorithms like DFS will become second nature. 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. 10.56201/ijcsmt.v9.no1.2023.pg1.12. https://towardsdatascience.com/deep-first-search-fundamental-graph-algorithm-d22991d5c144?source=rss—-7f60cf5620c9—4
[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 https://towardsdatascience.com/deep-first-search-fundamental-graph-algorithm-d22991d5c144?source=rss—-7f60cf5620c9—4