In this post, we implement Depth-First Search (DFS) in Java using an adjacency matrix and recursion. DFS is a fundamental graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. It is used in cycle detection, topological sorting, maze solving, and AI game tree searches.
What is DFS?
DFS explores a graph by diving deep into one branch before exploring others. In this implementation, we use a recursive approach: starting from node 1, we immediately follow the first unvisited neighbour, then the first unvisited neighbour of that node, and so on. Only when we reach a dead end do we backtrack and try the next neighbour.
The graph is represented as an adjacency matrix. An array q[] is used both as the visited set and to record the traversal order. The variable qpos tracks how many nodes have been visited so far.
Java Code Implementation
// ============================================================
// Depth-First Search (DFS) in Java
// Graph is represented as an adjacency matrix.
// DFS explores each branch recursively before backtracking.
// ============================================================
import java.io.*;
import java.util.*;
// Entry point class
class DFSDemo {
public static void main(String[] args) throws IOException {
DFS dfs = new DFS(); // Instantiating DFS triggers input, traversal, and output
}
}
// DFS graph traversal class
class DFS {
int[][] m = new int[50][50]; // Adjacency matrix — m[i][j]=1 means edge between i+1 and j+1
int n; // Number of nodes
int i, j, k, l; // Loop variables and visited flag
int[] q = new int[100]; // Traversal order array (acts as visited list too)
int qpos; // Number of nodes visited so far
public DFS() throws IOException {
BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
// ----- INPUT SECTION -----
System.out.println("Enter number of nodes (n):");
n = Integer.parseInt(obj.readLine());
System.out.println("Enter adjacency matrix (row by row, one value per line):");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
m[i][j] = Integer.parseInt(obj.readLine());
}
}
// ----- PRINT ENTERED MATRIX -----
System.out.println("\nEntered adjacency matrix:");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
System.out.print(m[i][j] + " ");
}
System.out.println();
}
// ----- DFS TRAVERSAL -----
q[0] = 1; // Start from node 1 (1-indexed)
qpos = 1; // One node visited so far
i = 0; // Index into q[] — start processing from the first node
findDFS(q[i] - 1); // Begin recursive DFS from node 1 (0-indexed: index 0)
// ----- OUTPUT -----
System.out.println("\nDFS Traversal Order:");
for (j = 0; j < qpos; j++) {
System.out.print(q[j] + " ");
}
System.out.println();
}
// Recursive DFS method
// a = 0-indexed row of the current node being processed
public void findDFS(int a) {
int c = a;
for (j = c; j < n; j++) {
if (m[c][j] != 0) { // Edge exists between node c+1 and j+1
// Check if node j+1 has already been visited
l = 0; // Reset flag: 0 = not visited
for (k = 0; k < qpos; k++) {
if (q[k] == j + 1) {
l = 1; // Already visited
}
}
if (l == 0) { // Not visited — add and recurse
q[qpos] = j + 1;
qpos++;
findDFS(j); // Recurse immediately (depth-first)
}
}
}
}
}
Explanation of the Code
- Adjacency Matrix — The graph is stored as a 50×50 integer array. The user fills an
n×nsubgrid where a1at[i][j]indicates an edge between nodei+1and nodej+1. - Starting Point — Node 1 is placed in
q[0]as the traversal starting point.findDFS(0)is then called with index0(the 0-based row for node 1). - Recursive
findDFS()— For each unvisited neighbour found at rowc, the method immediately adds it toq[]and calls itself recursively on that neighbour. This is what makes the traversal depth-first: we go as deep as possible before checking the next sibling. - Visited Check — Before adding a node, we scan the entire
q[]array to see if it is already present. The flaglis set to 1 if found, preventing cycles and duplicate visits.
Sample Input
Enter number of nodes (n):
8
Enter adjacency matrix (row by row, one value per line):
0 1 1 1 0 0 0 0
1 0 0 0 1 1 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
This is the same 8-node graph used in the BFS example, so you can directly compare the traversal orders. Node 1 connects to 2, 3, 4. Node 2 connects to 5, 6. Node 4 connects to 7, 8.
Sample Output
Entered adjacency matrix:
0 1 1 1 0 0 0 0
1 0 0 0 1 1 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
DFS Traversal Order:
1 2 5 6 3 4 7 8
Step-by-Step Output Explanation
- Start: Node 1 is placed in
q[0].findDFS(0)is called. - Node 1 → Node 2: First unvisited neighbour of node 1 is node 2. Add node 2 to
qand recurse:findDFS(1). - Node 2 → Node 5: First unvisited neighbour of node 2 (after index 1) is node 5. Add and recurse:
findDFS(4). - Node 5 → Node 6: Node 5’s neighbour is node 2 (visited) and node 6 (unvisited). Add 6 and recurse:
findDFS(5). Node 6 has no new neighbours. Return. - Backtrack to Node 1 → Node 3: After exploring the branch through nodes 2→5→6, DFS backtracks to node 1 and visits node 3 (next unvisited). Node 3 has no new neighbours. Backtrack again.
- Node 1 → Node 4 → Nodes 7 and 8: Next unvisited neighbour of node 1 is node 4. Recurse into node 4, which leads to nodes 7 and 8.
- Final output:
1 2 5 6 3 4 7 8— notice how DFS dives deep (1→2→5→6) before backtracking to visit siblings (3, 4), unlike BFS which would visit 2, 3, 4 first.
See Also
Conclusion
DFS is a simple yet powerful traversal strategy that naturally lends itself to recursive implementation. Comparing the output of this DFS (1 2 5 6 3 4 7 8) with the BFS output (1 2 3 4 5 6 7 8) on the same graph makes the difference concrete: BFS spreads wide, DFS dives deep. For production code, consider using Java’s built-in Stack or an iterative approach to avoid stack overflow on very deep graphs. Both BFS and DFS are foundational to understanding more advanced graph algorithms such as Dijkstra’s shortest path and A* search.
No Comments yet!