When learning about algorithms and data structures, one of the most fascinating and useful techniques you’ll encounter is Depth-First Search (DFS). It’s a simple yet powerful algorithm used to explore nodes and edges in a graph or tree. DFS works by starting at a source node and exploring as far as possible along each branch before backtracking. It’s like diving deep into a path until there’s nowhere left to go, and then retracing your steps to find unexplored routes.
with hands-on learning.
get the skills and confidence to land your next move.
Depth-First Search is used in a variety of real-world applications, from finding paths in mazes to analyzing networks, detecting cycles in graphs, and solving puzzles. It’s also used in artificial intelligence, topological sorting, and game development. The beauty of DFS lies in its simplicity—it mimics how a human might explore a set of connected paths. In this article, we’ll explore multiple ways to implement Depth-First Search in Java, including recursive and iterative methods, working with adjacency lists and matrices, and even accepting user input for flexibility.
Program 1: Simple Recursive DFS in Java
This is the most common and intuitive way to perform a Depth-First Search. In this method, we use recursion to visit each node, exploring all its connected neighbors.
import java.util.*;
public class DFSRecursive {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);
}
public void dfs(int node, Set<Integer> visited) {
visited.add(node);
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
public static void main(String[] args) {
DFSRecursive dfsGraph = new DFSRecursive();
dfsGraph.addEdge(0, 1);
dfsGraph.addEdge(0, 2);
dfsGraph.addEdge(1, 3);
dfsGraph.addEdge(2, 4);
Set<Integer> visited = new HashSet<>();
System.out.println("DFS starting from node 0:");
dfsGraph.dfs(0, visited);
}
}This recursive approach starts from a given node, marks it as visited, and explores all its unvisited neighbors. The recursion continues until all connected nodes are explored. This version is very beginner-friendly because it follows the natural structure of the DFS algorithm—exploring one node deeply before moving on to the next.
Program 2: Iterative DFS Using Stack
Recursion is simple, but it can lead to stack overflow for very large graphs. To overcome this, we can implement DFS iteratively using a stack.
import java.util.*;
public class DFSIterative {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);
}
public void dfsIterative(int start) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
System.out.print(node + " ");
visited.add(node);
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
public static void main(String[] args) {
DFSIterative graph = new DFSIterative();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
System.out.println("Iterative DFS starting from node 0:");
graph.dfsIterative(0);
}
}In this version, a stack is used to manage the traversal order. Each time we visit a node, we push its neighbors onto the stack. The algorithm continues until the stack becomes empty. This approach is more memory-efficient for large graphs and helps beginners understand how recursion can be replaced with a stack for better control.
Program 3: DFS for Directed Graphs
Depth-First Search also works perfectly on directed graphs. The only difference is that each edge now has a direction, so we only follow the edge in one direction when traversing.
import java.util.*;
public class DFSDirected {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);
}
public void dfs(int node, Set<Integer> visited) {
visited.add(node);
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
public static void main(String[] args) {
DFSDirected graph = new DFSDirected();
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
Set<Integer> visited = new HashSet<>();
System.out.println("DFS traversal of Directed Graph starting from node 0:");
graph.dfs(0, visited);
}
}In this program, DFS only follows the edges in their specified direction. This type of graph is used when modeling one-way relationships, such as web page links or roads with one-way traffic. The logic remains the same as before, but directionality affects which nodes are reachable.
Program 4: DFS Using Adjacency Matrix
While adjacency lists are common, graphs can also be represented as adjacency matrices, where each cell (i, j) represents a connection between nodes i and j. This program demonstrates how to perform DFS using that approach.
public class DFSMatrix {
public static void dfs(int[][] graph, int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int i = 0; i < graph.length; i++) {
if (graph[node][i] == 1 && !visited[i]) {
dfs(graph, i, visited);
}
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
boolean[] visited = new boolean[graph.length];
System.out.println("DFS traversal using Adjacency Matrix starting from node 0:");
dfs(graph, 0, visited);
}
}In this method, the DFS function checks the adjacency matrix to find connected nodes. If a node is connected and not yet visited, the function recursively explores it. Adjacency matrices are great for dense graphs where most nodes are connected to each other.
Program 5: DFS with User Input
Finally, let’s make our DFS program interactive. This version allows the user to enter the number of nodes, edges, and connections manually.
import java.util.*;
public class DFSUserInput {
private Map<Integer, List<Integer>> graph = new HashMap<>();
public void addEdge(int u, int v) {
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);
}
public void dfs(int node, Set<Integer> visited) {
visited.add(node);
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
DFSUserInput graph = new DFSUserInput();
System.out.print("Enter number of edges: ");
int edges = sc.nextInt();
System.out.println("Enter edges (u v): ");
for (int i = 0; i < edges; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.addEdge(u, v);
}
System.out.print("Enter starting node: ");
int start = sc.nextInt();
Set<Integer> visited = new HashSet<>();
System.out.println("DFS traversal starting from node " + start + ":");
graph.dfs(start, visited);
}
}This interactive program helps beginners experiment with different graph structures without changing the code. By allowing user input, it’s easier to visualize and understand how DFS behaves with different types of graphs and edges.
Frequently Asked Questions (FAQ)
Below are some of the most common questions students often ask when learning Depth-First Search in Java.
Q1: What is Depth-First Search?
Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Q2: What are the uses of DFS?
DFS is used in pathfinding, solving mazes, detecting cycles, topological sorting, and analyzing connectivity in graphs.
Q3: How is DFS different from BFS?
DFS explores one branch deeply before moving to another, while BFS explores all neighbors at the same level before going deeper.
Q4: Can DFS handle disconnected graphs?
Yes, but you need to run DFS for every unvisited node to ensure all components are explored.
Q5: Which is better — recursive or iterative DFS?
Both are effective. Recursion is simpler to understand, while iteration using a stack avoids stack overflow and is better for large graphs.
Conclusion
Depth-First Search is one of the most fundamental algorithms every Java programmer should understand. It’s not only useful in graph theory but also forms the foundation of many advanced algorithms. In this article, we explored five different implementations of DFS in Java — from simple recursive and iterative methods to working with adjacency matrices and user input.
Each version gives you a better understanding of how DFS works internally and how flexible it can be. The best way to master DFS is through practice — try modifying these programs, add more nodes, or even visualize the traversal steps. With time and experimentation, you’ll find DFS to be one of the most intuitive and powerful tools in your programming toolkit.
