Depth-First Search — Fundamental Graph Algorithm

Depth-First Search — Fundamental Graph Algorithm

Python recursive implementation of DFS algorithm with examples and step-by-step explanations

Introduction

In computer science, algorithms are the backbone of various useful technologies (like AI), helping us efficiently tackle a wide range of real-life challenges. Among these, graph algorithms hold a special place due to their applicability as many problems can be modeled using graphs. A graph is a collection of nodes (or vertices) connected by edges, representing relationships (or connections) between nodes.

Some examples:

• Social Networks: In a social network, like Facebook or Instagram, users can be represented as nodes, and friendships or connections between them are edges. [1]
• Route Planning and Navigation: In maps, locations (cities, intersections, or landmarks) are modeled as nodes, and roads or paths between them are edges. [2]
• Web Crawling: The web can be seen as a massive graph where web pages are nodes, and hyperlinks between them are edges.
• Scheduling and Task Management: Many task dependencies can be modeled as directed acyclic graphs (DAGs), where tasks are nodes and dependencies between them are edges.
• Network Connectivity: In computer networks, devices (routers, computers) are nodes, and communication links are edges.

One of the fundamental algorithms used to traverse or explore graphs is Depth First Search (DFS). It is used to explore (visit) all nodes in the graph. Another, complementary and fundamental algorithm to accomplish that goal is called Breadth First Search (BFS) which will be a subject of a separate article.

Here, we will dive into how DFS works, with simple code, intuitive examples, and some cool animations showing you how this algorithm works step-by-step.

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. [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]

Depth-First Search — Fundamental Graph Algorithm was originally published in Towards Data Science on Medium, where people are continuing the conversation by highlighting and responding to this story.