Graph traversal is the process of visiting all nodes in a graph in a systematic order. It is a fundamental operation in graph algorithms used for pathfinding, connectivity analysis, cycle detection, and more. There are two standard traversal strategies:
- Breadth-First Search (BFS) — Explores all neighbours of the current node before going deeper. Uses a queue internally.
- Depth-First Search (DFS) — Explores as far as possible along each branch before backtracking. Uses recursion (implicit call stack) internally.
In this post, we implement both BFS and DFS on an undirected graph represented as an adjacency matrix.
Java Program: BFS and DFS Graph Traversal
package graphtraversal;
import java.io.*;
// Simple queue used for BFS traversal
class BFSQueue {
public int front, rear, capacity, queue[];
public BFSQueue() {
capacity = 20;
queue = new int[capacity];
front = 0;
rear = -1;
}
public boolean isFull() {
return rear == capacity - 1;
}
public boolean isEmpty() {
return rear < front;
}
// Adds a vertex index to the rear of the queue
public void enqueue(int vertexIndex) {
if (isFull()) {
System.out.println("Queue is full - cannot enqueue");
} else {
rear++;
queue[rear] = vertexIndex;
}
}
// Removes and returns the front vertex index
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
} else {
int vertexIndex = queue[front];
front++;
return vertexIndex;
}
}
}
// Graph using an adjacency matrix; supports BFS and DFS traversal
class Graph {
BFSQueue bfsQueue = new BFSQueue();
int adjacencyMatrix[][]; // adjacencyMatrix[i][j] = 1 means edge between i and j
int bfsVisitedOrder[]; // Records order vertices were visited in BFS
int dfsVisitedOrder[]; // Records order vertices were visited in DFS
int numVertices; // Total number of vertices
int bfsVisitCount; // How many vertices added to BFS order
int dfsVisitCount; // How many vertices added to DFS order
public Graph(int[][] matrix, int vertexCount) {
adjacencyMatrix = matrix;
numVertices = vertexCount;
bfsVisitedOrder = new int[numVertices];
dfsVisitedOrder = new int[numVertices];
bfsVisitCount = 0;
dfsVisitCount = 0;
}
// BFS starting from the given start vertex
public void bfs(int startVertex) {
bfsQueue.enqueue(startVertex);
bfsVisitedOrder[bfsVisitCount] = startVertex;
bfsVisitCount++;
while (!bfsQueue.isEmpty()) {
int currentVertex = bfsQueue.dequeue();
for (int neighbour = 0; neighbour < numVertices; neighbour++) {
if (adjacencyMatrix[currentVertex][neighbour] == 1
&& !isAlreadyVisitedBFS(neighbour)) {
bfsQueue.enqueue(neighbour);
bfsVisitedOrder[bfsVisitCount] = neighbour;
bfsVisitCount++;
}
}
}
System.out.print("BFS traversal: ");
for (int i = 0; i < numVertices; i++) {
System.out.print(bfsVisitedOrder[i] + " ");
}
System.out.println();
}
private boolean isAlreadyVisitedBFS(int vertex) {
for (int i = 0; i < numVertices; i++) {
if (bfsVisitedOrder[i] == vertex) return true;
}
return false;
}
// DFS starting from the given vertex (recursive)
public void dfs(int currentVertex) {
dfsVisitedOrder[dfsVisitCount] = currentVertex;
dfsVisitCount++;
for (int neighbour = 0; neighbour < numVertices; neighbour++) {
if (adjacencyMatrix[currentVertex][neighbour] == 1
&& !isAlreadyVisitedDFS(neighbour)) {
dfs(neighbour);
}
}
}
public void printDFS() {
System.out.print("DFS traversal: ");
for (int i = 0; i < numVertices; i++) {
System.out.print(dfsVisitedOrder[i] + " ");
}
System.out.println();
}
private boolean isAlreadyVisitedDFS(int vertex) {
for (int i = 0; i < numVertices; i++) {
if (dfsVisitedOrder[i] == vertex) return true;
}
return false;
}
}
public class GraphTraversal {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter number of vertices: ");
int numVertices = Integer.parseInt(reader.readLine());
int[][] adjacencyMatrix = new int[numVertices][numVertices];
System.out.println("Enter adjacency matrix (" + numVertices + "x" + numVertices + "), one value per line:");
for (int row = 0; row < numVertices; row++) {
for (int col = 0; col < numVertices; col++) {
adjacencyMatrix[row][col] = Integer.parseInt(reader.readLine());
}
}
Graph graph = new Graph(adjacencyMatrix, numVertices);
System.out.print("Enter starting vertex: ");
int startVertex = Integer.parseInt(reader.readLine());
graph.bfs(startVertex);
graph.dfs(startVertex);
graph.printDFS();
}
}
How the Code Works
- Graph representation — The graph is stored as an adjacency matrix.
adjacencyMatrix[i][j] = 1means there is an edge between vertexiand vertexj. - BFS — Uses a queue. The start vertex is enqueued and marked visited. Then, the algorithm dequeues a vertex and enqueues all its unvisited neighbours, recording visit order.
- DFS — Uses recursion. The start vertex is marked visited, then for each unvisited neighbour, DFS is called recursively. This naturally explores depth-first.
- Visited tracking — Both BFS and DFS maintain an ordered array of visited vertices. The
isAlreadyVisitedhelpers search this array to prevent revisiting. - Input format — The adjacency matrix is entered row by row, one integer per line (0 = no edge, 1 = edge).
Sample Output
Enter number of vertices: 7
Enter adjacency matrix (7x7), one value per line:
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
Enter starting vertex: 0
BFS traversal: 0 1 2 3 4 5 6
DFS traversal: 0 1 3 4 2 5 6Output Explanation
- BFS (0 1 2 3 4 5 6) — From vertex 0, all immediate neighbours are visited first (level 1), then their neighbours next (level 2). This level-by-level expansion is the hallmark of BFS.
- DFS (0 1 3 4 2 5 6) — From vertex 0, DFS immediately dives into neighbour 1, then into 3, then into 4. Only when there are no more unvisited neighbours does it backtrack. The result reflects the depth-first exploration path.
See Also
- Implementing Binary Search Tree in Java — Tree traversal concepts closely related to DFS
- Java Implementation of Queue using Linked List — The queue data structure driving BFS
- Implementation of Stack in Java — DFS can also be implemented iteratively using an explicit stack
- Implementing Quick Sort in Java — Another divide-and-conquer algorithm on ordered collections
Conclusion
BFS and DFS are the two foundational algorithms for exploring graphs. BFS is ideal for finding the shortest path in an unweighted graph, while DFS is better suited for tasks like cycle detection, topological sorting, and solving maze problems. Understanding both traversal strategies — and knowing when to apply each — is an essential skill in software engineering and algorithm design.