Implementation of DFS Algorithm in Java

Depth First Search (DFS) is a powerful tool for exploring graphs, and understanding how to implement it is key to solving many computer science problems. In this article, we’ll focus on how to write a DFS algorithm in Java.

Tip

Before diving into the implementation, it’s helpful to have a good understanding of what graphs are and the basic idea behind Depth First Search. You can learn more about them in these articles:

Representing a Graph in Java

Before we can implement DFS, we need a way to represent our graph in Java. Two common ways to do this are using an adjacency list or an adjacency matrix.

Adjacency List

An adjacency list represents the graph as a HashMap where each key is a node, and its value is a List of its neighboring nodes. This is efficient for sparse graphs (graphs with fewer connections).

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    public void addVertex(String vertex) {
        adjList.put(vertex, new ArrayList<>());
    }

    public void addEdge(String source, String destination) {
        adjList.get(source).add(destination);
        // For undirected graphs, you would also add:
        // adjList.get(destination).add(source);
    }

    public Map<String, List<String>> getAdjList() {
        return adjList;
    }
}

In this example:

  • The Graph class uses a HashMap called adjList to store the adjacency list.
  • The keys in the HashMap are the vertices (nodes) of the graph, represented as String objects.
  • The values in the HashMap are List<String> objects, where each list contains the neighbors of the corresponding vertex.
  • The addVertex method adds a new vertex to the graph by creating a new entry in the adjList map with an empty list of neighbors.
  • The addEdge method adds an edge between two vertices by adding the destination vertex to the list of neighbors of the source vertex. For undirected graphs, you would also add the source vertex to the list of neighbors of the destination vertex.

Adjacency Matrix

An adjacency matrix represents the graph as a 2D array where matrix[i][j] = true if there’s an edge from vertex i to vertex j, and false otherwise. It’s simpler to implement but uses more memory, especially for sparse graphs.

public class Graph {
    private boolean[][] adjMatrix;
    private int numVertices;

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        this.adjMatrix = new boolean[numVertices][numVertices];
    }

    public void addEdge(int i, int j) {
        adjMatrix[i][j] = true;
        adjMatrix[j][i] = true;  // For undirected graphs
    }

    public void removeEdge(int i, int j) {
        adjMatrix[i][j] = false;
        adjMatrix[j][i] = false; // For undirected graphs
    }

    public boolean isEdge(int i, int j) {
        return adjMatrix[i][j];
    }
}

In this example:

  • The Graph class uses a 2D boolean array called adjMatrix to represent the adjacency matrix.
  • The numVertices variable stores the number of vertices in the graph.
  • The constructor initializes the adjacency matrix with the specified number of vertices.
  • The addEdge method adds an edge between two vertices by setting the corresponding entry in the adjacency matrix to true. For undirected graphs, it also sets the entry in the opposite direction to true.
  • The removeEdge method removes an edge between two vertices by setting the corresponding entry in the adjacency matrix to false. For undirected graphs, it also sets the entry in the opposite direction to false.
  • The isEdge method checks if there is an edge between two vertices by returning the value of the corresponding entry in the adjacency matrix.

In this article, we will focus on representing graphs using the adjacency list, as it’s often more efficient for DFS.

Recursive DFS Implementation

The most common and intuitive way to implement DFS is using recursion. Here’s how it works:

  1. Mark the current node as visited. We use a HashSet called visited to keep track of visited nodes.
  2. Process the current node. This could involve printing the node’s value, adding it to a list, or performing any other action.
  3. Explore the neighbors. For each neighbor of the current node:
    • If the neighbor hasn’t been visited yet, recursively call the DFS function on that neighbor.

Here’s the Java code for the recursive DFS:

import java.util.*;

public class DFS {

    public static void dfsRecursive(Graph graph, String node, Set<String> visited) {
        if (visited == null) {
            visited = new HashSet<>();
        }

        if (!visited.contains(node)) {
            visited.add(node);
            System.out.print(node + " "); // Process the node (e.g., print it)

            List<String> neighbors = graph.getAdjList().get(node);
            if (neighbors != null) {
                for (String neighbor : neighbors) {
                    dfsRecursive(graph, neighbor, visited);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");

        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("E", "F");

        System.out.println("DFS Traversal (Recursive):");
        dfsRecursive(graph, "A", new HashSet<>()); // Start DFS from node 'A'
        System.out.println(); // Add a newline for clarity
    }
}

Here’s how you might use this function:

DFS Traversal (Recursive):
A B D E F C
  • The function dfsRecursive takes the graph, the current node, and a visited set as input.
  • If visited is null (not provided in the initial call), we create an empty HashSet to store visited nodes.
  • We check if the current node is in the visited set. If it’s not, we add it to the set and process it (in this case, print it).
  • Then, we iterate through the neighbors of the current node and recursively call dfsRecursive for each unvisited neighbor.

Iterative DFS Implementation using a Stack

An alternative to recursion is to use an iterative approach with a stack. This can be helpful to avoid stack overflow errors that can occur with deep recursion.

Here’s the iterative approach:

  1. Create a stack and add the starting node to it.
  2. Create a set to keep track of visited nodes.
  3. While the stack is not empty:
    • Pop a node from the stack.
    • If the node hasn’t been visited:
      • Mark it as visited.
      • Process the node (e.g., print it).
      • Add all its unvisited neighbors to the stack.

Here’s the Java code for the iterative DFS:

import java.util.*;

public class DFS {

    public static void dfsIterative(Graph graph, String startNode) {
        Set<String> visited = new HashSet<>(); // Keep track of visited nodes
        Stack<String> stack = new Stack<>(); // Use a Stack

        stack.push(startNode); // Add the starting node

        System.out.println("DFS Traversal (Iterative):");
        while (!stack.isEmpty()) {
            String node = stack.pop(); // Pop the top node

            if (!visited.contains(node)) {
                visited.add(node);
                System.out.print(node + " "); // Process the node

                List<String> neighbors = graph.getAdjList().get(node);
                if (neighbors != null) {
                    // Add neighbors to the stack in reverse order to maintain DFS order
                    for (int i = neighbors.size() - 1; i >= 0; i--) {
                        String neighbor = neighbors.get(i);
                        if (!visited.contains(neighbor)) {
                            stack.push(neighbor);
                        }
                    }
                }
            }
        }
        System.out.println(); // Add a newline for clarity
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");

        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("E", "F");

        dfsIterative(graph, "A");
    }
}

Here’s how you might use this function:

DFS Traversal (Iterative):
A C F B E D
  • We initialize a visited set and a stack.
  • We push the startNode onto the stack.
  • The while loop continues as long as there are nodes in the stack.
  • Inside the loop, we pop a node from the stack. This is the node we’ll explore next.
  • If the node hasn’t been visited, we mark it as visited and process it.
  • We find all neighbors of the current node. For each neighbor that hasn’t been visited yet, we push it to the stack.
  • Note that we are iterating the neighbors in reversed order so that the visit sequence match closer to the recursive version of DFS.

Choosing Between Recursive and Iterative

  • Recursive DFS: Is often simpler to write and understand, closely matching the definition of DFS. However, it can lead to a StackOverflowError if the graph is very deep.
  • Iterative DFS: Is more robust against deep graphs, as it uses heap memory for the stack. The logic might feel slightly less direct than recursion.

Both implementations have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges. The space complexity is O(V) in the worst case, as we need to store all vertices in the visited set and the stack (in the iterative version) or the call stack (in the recursive version). You can refer to this article to dive deeper into the time and space complexity of DFS.

What’s Next?

Now that you’ve learned how to implement DFS in Java, you can explore other related articles: