Traverse a Graph Using BFS and DFS in Java
Problem
A graph is a set of nodes joined by edges; breadth-first search (BFS) explores neighbours level by level, while depth-first search (DFS) follows one path as far as possible before backing up.
Store an undirected graph of six nodes as an adjacency list, then list the order in which BFS and DFS visit the nodes starting from node 0.
Java Program
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class GraphBfsDfs {
static List<List<Integer>> graph = new ArrayList<>();
static void addEdge(int u, int v) { // undirected: store the edge both ways
graph.get(u).add(v);
graph.get(v).add(u);
}
static List<Integer> bfs(int start) {
List<Integer> order = new ArrayList<>();
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new ArrayDeque<>();
queue.add(start);
visited[start] = true; // mark when queued, so no node is queued twice
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : graph.get(node)) {
if (!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
return order;
}
static void dfs(int node, boolean[] visited, List<Integer> order) {
visited[node] = true;
order.add(node);
for (int next : graph.get(node)) {
if (!visited[next]) dfs(next, visited, order); // go as deep as possible first
}
}
public static void main(String[] args) {
for (int i = 0; i < 6; i++) graph.add(new ArrayList<>());
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(2, 3);
addEdge(2, 4);
addEdge(3, 5);
addEdge(4, 5);
System.out.println("BFS from 0: " + bfs(0));
List<Integer> dfsOrder = new ArrayList<>();
dfs(0, new boolean[graph.size()], dfsOrder);
System.out.println("DFS from 0: " + dfsOrder);
}
}Output
Core Logic
Both traversals share a visited array so no node is processed twice; the only difference is the order in which waiting nodes are taken — first-in-first-out for BFS, deepest-first for DFS.
- 1
graph.get(u)holds every neighbour of nodeu;addEdgerecords each edge in both directions. - 2BFS takes nodes from the front of a queue and adds unvisited neighbours to the back, marking them visited as they're queued.
- 3DFS marks a node, then immediately recurses into its first unvisited neighbour before trying the next.
- 4Both methods record the visiting order in a list, which is printed.
Key Point: Marking a node as visited when it's queued, not when it's dequeued, stops BFS from adding the same node to the queue several times.
Why: Each vertex is visited once and each edge examined a constant number of times; the visited array and queue or call stack hold at most V nodes.
Key Concepts
Approach 2: Shortest Path with BFS
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
public class GraphShortestPathBfs {
public static void main(String[] args) {
int n = 6;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}};
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
int[] parent = new int[n];
int[] dist = new int[n];
Arrays.fill(dist, -1); // -1 = not reached yet
Queue<Integer> queue = new ArrayDeque<>();
queue.add(0);
dist[0] = 0;
parent[0] = -1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : graph.get(node)) {
if (dist[next] == -1) {
dist[next] = dist[node] + 1; // one edge further than its parent
parent[next] = node;
queue.add(next);
}
}
}
List<Integer> path = new ArrayList<>();
for (int at = 5; at != -1; at = parent[at]) path.add(at); // walk back from the target
Collections.reverse(path);
System.out.println("Distances from 0: " + Arrays.toString(dist));
System.out.println("Shortest path 0 -> 5: " + path + " (" + dist[5] + " edges)");
}
}
Output
Core Logic
Because BFS reaches nodes in order of distance, the first time it reaches a node is along a shortest path — so recording each node's parent lets the path be rebuilt.
- 1
diststarts at -1 for every node except the start, which is 0. - 2When a neighbour is first reached, its distance is the current node's plus one, and its
parentis the current node. - 3Following
parentlinks back from node 5 to the start gives the path in reverse. - 4
Collections.reverseputs it in start-to-target order.
Key Point: This works only for unweighted graphs; when edges have different lengths, use Dijkstra's algorithm instead.
Why: It's a single BFS plus a walk back along at most V parent links.
Key Concepts
Interview Questions
When should you use BFS instead of DFS?
BFS finds the shortest path in an unweighted graph and explores level by level. DFS uses less memory on wide graphs and suits tasks such as cycle detection and topological sorting.
How do you detect a cycle in an undirected graph with DFS?
During DFS, reaching an already-visited neighbour that isn't the node you came from means there's a cycle.