Depth-first search

For now, we know what a graph is, how to formally describe its structure and store it on a computer. This basic knowledge is important, but we need something more to efficiently handle graph-based tasks. To be able to solve a variety of tasks, we also need to get familiar with appropriate processing algorithms. They will allow us to analyze the structure of graphs in more detail and gain the needed information from them.

One such algorithm is the depth-first search — a simple graph traversal procedure often used as a building block for many other graph processing algorithms. This algorithm will be the main focus of this topic: we will learn the details of the procedure and see how it works on an example.

Depth-first search algorithm

For a graph $G$, the depth-first search (DFS) procedure consists of the following steps:

1. Choose an arbitrary unvisited node $v$ of a graph $G$.

2. Consider all the unvisited neighbors of the current node $v$ and recursively visit each of them.

3. Repeat steps 1-2 until all nodes are visited.

DFS is a recursive algorithm. If the current node has unvisited neighbors, the DFS procedure is applied for each of them. The process continues until all nodes of the graph have been visited.

An example

To get a better understanding of the procedure, let's see how it works for the following graph:

The figures below show the procedure step-by-step. The current node is shown in bold blue, the visited nodes are shown in blue, and the unvisited neighbors of the current node are green.

First, we choose an arbitrary node to start with. For the given graph, this node is $0$. Initially, the node has two unvisited neighbors: $1$ and $2$. We choose the node $1$ as the next node to process and run the DFS procedure for this node. At the second step, we recursively call DFS for the node $3$, since it is the only unvisited node of $1$.

Next, we consider all unvisited neighbors of the node $3$, which are $2$ and $5$. We choose the node $2$ and apply DFS for it. After that, we can see that the node $2$ doesn't have any unvisited neighbors. So, the node is processed and we return to the previous node in the order of recursive calls.

At the 5th step, we again have only one node to move on to. We recursively call DFS for the node $5$ and move to the next step.

After we visit all nodes, the graph will look like this:

An important thing here is that the blue nodes and edges form a tree. Such a tree is called a spanning tree since it connects (spans) all the nodes of the graph. At this point, one of the applications of the depth-first search procedure is the construction of a spanning tree in a graph.

Another interesting application of DFS is maze traversing. A maze can be represented as an undirected graph with edges corresponding to maze paths and nodes corresponding to their intersections. To understand how exactly it works, take a look at this video. Also, you may check out a visualization of DFS for arbitrary graphs.

Pseudocode

In this section, we present the pseudocode representation of the Depth-First Search (DFS) algorithm, a fundamental graph traversal procedure widely utilized in various graph processing tasks. DFS systematically explores the structure of a graph by visiting each node and its unvisited neighbors.

The DFS procedure involves initiating the traversal from an arbitrary unvisited node, recursively visiting its neighbors, and continuing this process until all nodes are visited. The algorithm creates a spanning tree that connects all nodes of the graph in a systematic manner.

// Depth-First Search (DFS) Algorithm

// Function to perform DFS on a graph
function DFS(graph):
    // Initialize a set to keep track of visited nodes
    visited = set()

    // Iterate through all nodes in the graph
    for node in graph:
        // If the node is not visited, apply DFS
        if node not in visited:
            helper(graph, node, visited)

// Helper function for recursive DFS traversal
function helper(graph, node, visited):
    // Mark the current node as visited
    visited.add(node)

    // Process the current node
    processNode(node)

    // Recursively visit all unvisited neighbors of the current node
    for neighbor in graph[node]:
        if neighbor not in visited:
            helper(graph, neighbor, visited)

// Function to process a node during DFS. 
// Customize it as needed, when using it as a building block for other advanced algorithms based on DFS.
function processNode(node):
    // Print or perform any desired operation on the node
    print("Visiting node:", node)

Complexity analysis

First of all, it is important to understand that the time complexity of the algorithm depends solely on the number of times we consider a neighbor in step two, i.e. the total number of times we consider an edge from the unvisited node whose neighbors we are processing. Each edge $\{x, y\}$ is considered exactly twice: while visiting $x$ and then while visiting $y$ (or vice versa). Therefore, the overall running time of the algorithm should be $2|E|$, that is $O(|E|)$. Unfortunately, in our graph, there might be isolated nodes, i.e. nodes with no neighbors. In this case, we still need to visit them once in step 1, which takes at most $|V|$ steps. Overall, we end up with the time complexity $O(|V| + |E|)$ for our algorithm.

Conclusion

In this topic, we focused on the depth-first search, an algorithm that allows us to go through all nodes of a graph. Depth-first search can help us process graphs, and we can also use it as a block to create other more complex algorithms.

The DFS algorithm is a recursive one, and it goes on until we visit all nodes of our graph. As a result, we will have a spanning tree that connects all nodes of the graph. Remember that the time complexity of this algorithm is $O(|V| + |E|)$. Now it's time to solve some tasks and make sure you'll be able to use the DFS algorithm in your future practice.