Graph Traversal — Depth First Search Algorithm

Deep dive into Depth First Search graph traversal algorithm.

Depth-First Search (DFS) is a popular graph traversal algorithm that explores as far as possible along each branch before backtracking. It traverses a graph in a depthward motion until it reaches a leaf node or a node with no unvisited neighbors, and then it backtracks to explore other branches.

DFS can be implemented using either recursive or iterative approaches. First, let’s focus on the recursive implementation.

Recursive DFS Implementation

1. Start the DFS algorithm by calling a recursive DFS helper function, passing in the source vertex as the starting point.
2. In the DFS helper function:

• Mark the current vertex as visited.
• Perform any necessary operations on the current vertex.
• Iterate through the neighbors of the current vertex.
• For each unvisited neighbor, recursively call the DFS helper function, passing in the neighbor as the new current vertex.

3. Repeat this process until all vertices have been visited.

Here’s a pseudocode representation of the recursive DFS algorithm:

function dfs(vertex):
    mark vertex as visited
    perform operations on vertex

    for each neighbor in vertex's neighbors:
        if neighbor is not visited:
            dfs(neighbor)

DFS Illustration

Recursive DFS Implementation in Java

Following code block shows the depth first search implementation in Java. This code is based on the Adjacency List implementation of a Graph as explained in my earlier posts in a Graph series.

    // DFS recursive implementation
    public void dfsRecursive(T startVertex) {
        System.out.println("DFS recursive traversal : ");
        Set<T> visited = new HashSet<>();
        dfsRecursiveHelper(startVertex, visited);
    }

    private void dfsRecursiveHelper(T vertex, Set<T> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");

        for (T neighbor : getNeighbors(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsRecursiveHelper(neighbor, visited);
            }
        }
    }

Let’s break down the code step by step:

The dfsRecursive method serves as the entry point for the DFS traversal. It takes a startVertex as its parameter and initiates the DFS process. It creates a visited set to keep track of the visited vertices and calls the dfsRecursiveHelper method to perform the actual traversal.

The dfsRecursiveHelper method is a recursive helper function responsible for exploring the graph. It takes a vertex and the visited set as parameters. Here's how it works:

1. We add the current vertex to the visited set to mark it as visited.
2. We print the vertex to show the order of traversal.
3. We iterate through the neighbors of the vertex by using the getNeighbors method, which returns a list of neighbors for a given vertex.
4. For each neighbor, we check if it is not already visited (!visited.contains(neighbor)). If it is not visited, we recursively call dfsRecursiveHelper with the neighbor as the new vertex and the visited set.
5. By recursively calling dfsRecursiveHelper, we explore the unvisited neighbors of the current vertex in a depth-first manner until there are no more unvisited neighbors.

This recursive approach allows us to traverse the graph in a depth-first fashion, visiting each vertex and exploring its unvisited neighbors until the entire graph is traversed.

Iterative DFS Implementation in Java

In the following code, we aim to traverse a graph using DFS in an iterative manner.

    // DFS iterative implementation
    public void dfsIterative(T startVertex) {
        System.out.println("DFS iterative traversal : ");
        Set<T> visited = new HashSet<>();
        Stack<T> stack = new Stack<>();
        stack.push(startVertex);

        while (!stack.isEmpty()) {
            T vertex = stack.pop();
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                System.out.print(vertex + " ");

                for (T neighbor : getNeighbors(vertex)) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        System.out.println("\n");
    }

The dfsIterative method serves as the entry point for the DFS traversal. It takes a startVertex as its parameter and initiates the DFS process.

Let's understand how the iterative approach works:

1. We create a visited set to keep track of the visited vertices and a stack to store the vertices for traversal.
2. We push the startVertex onto the stack to begin the traversal.
3. While the stack is not empty, we repeat the following steps:

• Pop a vertex from the stack and assign it to the vertex variable.
• Check if the vertex is not already visited (!visited.contains(vertex)).
• If the vertex is not visited:
• Add it to the visited set to mark it as visited.
• Print the vertex to show the order of traversal.
• Iterate through the neighbors of the vertex by using the getNeighbors method.
• For each neighbor, if it is not already visited, push it onto the stack.

4. Once the stack is empty, we have traversed the entire graph, and we print a newline to indicate the end of the traversal.

The iterative approach simulates the depth-first traversal by using a stack to keep track of the vertices to be explored. It starts with the initial vertex and explores its neighbors iteratively until there are no more unvisited vertices.

I hope this post helps you understand the DFS algorithm and its implementation. It is a fundamental algorithm for graph traversal and can be used to solve various graph-related problems.