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 aHashMap
calledadjList
to store the adjacency list. - The keys in the
HashMap
are the vertices (nodes) of the graph, represented asString
objects. - The values in the
HashMap
areList<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 theadjList
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 calledadjMatrix
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 totrue
. For undirected graphs, it also sets the entry in the opposite direction totrue
. - The
removeEdge
method removes an edge between two vertices by setting the corresponding entry in the adjacency matrix tofalse
. For undirected graphs, it also sets the entry in the opposite direction tofalse
. - 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:
- Mark the current node as visited. We use a
HashSet
calledvisited
to keep track of visited nodes. - Process the current node. This could involve printing the node’s value, adding it to a list, or performing any other action.
- 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 avisited
set as input. - If
visited
isnull
(not provided in the initial call), we create an emptyHashSet
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:
- Create a stack and add the starting node to it.
- Create a set to keep track of visited nodes.
- 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 astack
. - We push the
startNode
onto thestack
. - The
while
loop continues as long as there are nodes in thestack
. - Inside the loop, we
pop
a node from thestack
. 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, wepush
it to thestack
. - 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:
- Implementing DFS in other programming languages: DFS in C++, DFS in JavaScript, DFS in Python:
- Applications of DFS: Learn about the various problems DFS can solve, like finding connected components, cycle detection, and topological sorting.
- Common DFS Mistakes: Understand frequent errors in DFS implementations and how to avoid them.
- DFS Visualization: See DFS in action with visual examples and animations to build intuition.