Breadth-First Search (BFS) is one of the most fundamental and widely used algorithms in computer science. It is a graph traversal technique that explores all vertices of a graph level by level. Instead of diving deep into one branch like Depth-First Search (DFS), BFS visits all neighboring nodes first before moving on to the next level. This makes it particularly effective when you need to find the shortest path in an unweighted graph or explore all reachable nodes efficiently.
with hands-on learning.
get the skills and confidence to land your next move.
Understanding BFS is essential for programmers, especially those working in data structures, algorithms, and artificial intelligence. It has numerous real-world applications such as finding the shortest path in a network, web crawling, GPS route planning, and even solving puzzles. In this article, we’ll explore how to implement BFS in Java through multiple examples, using both iterative and recursive approaches. By the end, you’ll have a strong grasp of how BFS works and how you can apply it in your own Java projects.
Program 1: Basic Breadth-First Search Using Queue
This program demonstrates the most basic and straightforward way to perform BFS using a queue data structure. It traverses all nodes of a graph starting from a given node.
import java.util.*;
public class BFSExample1 {
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 bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
BFSExample1 bfs = new BFSExample1();
bfs.addEdge(0, 1);
bfs.addEdge(0, 2);
bfs.addEdge(1, 3);
bfs.addEdge(1, 4);
bfs.addEdge(2, 5);
System.out.println("Breadth-First Search starting from node 0:");
bfs.bfs(0);
}
}In this implementation, a queue is used to store nodes that need to be explored. The algorithm starts from the given node, visits its neighbors, and continues the process until all reachable nodes are explored. This version clearly demonstrates how BFS ensures that nodes are visited level by level, making it ideal for beginners to visualize how the algorithm works.
Program 2: BFS Using Adjacency Matrix
While the adjacency list representation is common, BFS can also be performed using an adjacency matrix. This version is helpful when working with dense graphs where most nodes are interconnected.
import java.util.*;
public class BFSExample2 {
public void bfs(int[][] graph, int start) {
boolean[] visited = new boolean[graph.length];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int i = 0; i < graph.length; i++) {
if (graph[node][i] == 1 && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
BFSExample2 bfs = new BFSExample2();
System.out.println("BFS traversal using adjacency matrix starting from node 0:");
bfs.bfs(graph, 0);
}
}Here, we represent the graph as a two-dimensional array where each cell (i, j) indicates whether a connection exists between node i and node j. The algorithm checks all nodes and explores unvisited ones connected to the current node. This form is ideal for students who want to understand how BFS can be applied when working with matrix-based data structures.
Program 3: BFS for Directed Graphs
This program applies BFS to a directed graph, where edges have direction. It demonstrates how BFS can adapt to graphs where the path from one node to another isn’t necessarily bidirectional.
import java.util.*;
public class BFSDirectedGraph {
private Map<Integer, List<Integer>> graph;
public BFSDirectedGraph() {
graph = new HashMap<>();
}
public void addEdge(int from, int to) {
graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
}
public void bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
BFSDirectedGraph g = new BFSDirectedGraph();
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
System.out.println("BFS in directed graph starting from node 1:");
g.bfs(1);
}
}Here, BFS handles the direction of edges by only following the forward connections from a node. This is especially useful in modeling one-way streets, dependency graphs, or workflow systems. Beginners can understand how the same BFS logic adapts seamlessly to both directed and undirected graphs.
Program 4: Recursive BFS Implementation
BFS is typically implemented iteratively, but we can simulate its behavior using recursion by processing nodes level by level.
import java.util.*;
public class BFSExample3 {
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 bfsRecursive(List<Integer> currentLevel, Set<Integer> visited) {
if (currentLevel.isEmpty()) return;
List<Integer> nextLevel = new ArrayList<>();
for (int node : currentLevel) {
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
nextLevel.add(neighbor);
}
}
}
bfsRecursive(nextLevel, visited);
}
public static void main(String[] args) {
BFSExample3 bfs = new BFSExample3();
bfs.addEdge(0, 1);
bfs.addEdge(0, 2);
bfs.addEdge(1, 3);
bfs.addEdge(1, 4);
bfs.addEdge(2, 5);
System.out.println("BFS traversal using recursion starting from node 0:");
bfs.bfsRecursive(Collections.singletonList(0), new HashSet<>(Collections.singleton(0)));
}
}This recursive approach helps beginners understand how BFS processes one level at a time. Although recursion is not the most efficient way to perform BFS, it gives valuable insight into how level-based traversal can be modeled without explicitly using a queue.
Program 5: BFS for Shortest Path in an Unweighted Graph
One of the most useful applications of BFS is finding the shortest path between two nodes in an unweighted graph.
import java.util.*;
public class BFSExample4 {
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 shortestPath(int start, int target) {
Queue<Integer> queue = new LinkedList<>();
Map<Integer, Integer> parent = new HashMap<>();
Set<Integer> visited = new HashSet<>();
queue.add(start);
visited.add(start);
parent.put(start, -1);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == target) break;
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
parent.put(neighbor, node);
queue.add(neighbor);
}
}
}
List<Integer> path = new ArrayList<>();
int current = target;
while (current != -1) {
path.add(current);
current = parent.get(current);
}
Collections.reverse(path);
System.out.println("Shortest path from " + start + " to " + target + ": " + path);
}
public static void main(String[] args) {
BFSExample4 bfs = new BFSExample4();
bfs.addEdge(0, 1);
bfs.addEdge(0, 2);
bfs.addEdge(1, 3);
bfs.addEdge(1, 4);
bfs.addEdge(2, 5);
bfs.addEdge(4, 5);
bfs.shortestPath(0, 5);
}
}In this version, BFS keeps track of each node’s parent to reconstruct the shortest path once the target is reached. This is particularly valuable in applications like routing or social networks, where identifying the minimum number of connections between two points is important.
Program 6: BFS with User Input
This program allows users to create their own graph and perform BFS on it. It helps learners experiment and understand BFS dynamically.
import java.util.*;
public class BFSExample5 {
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 bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BFSExample5 bfs = new BFSExample5();
System.out.print("Enter number of edges: ");
int edges = sc.nextInt();
for (int i = 0; i < edges; i++) {
System.out.print("Enter edge (u v): ");
int u = sc.nextInt();
int v = sc.nextInt();
bfs.addEdge(u, v);
}
System.out.print("Enter the starting node: ");
int start = sc.nextInt();
System.out.println("BFS traversal starting from node " + start + ":");
bfs.bfs(start);
}
}By allowing users to enter their own graph structure, this program makes BFS interactive. It’s great for beginners who want to test different scenarios and see how BFS behaves with various inputs and graph configurations.
Frequently Asked Questions (FAQ)
Here are some common questions beginners often ask when learning BFS in Java.
Q1: What is Breadth-First Search (BFS)?
BFS is a graph traversal algorithm that explores all nodes level by level before moving deeper into the structure.
Q2: What data structure is used in BFS?
A queue is used in BFS to keep track of nodes that need to be visited in order.
Q3: What is the main difference between BFS and DFS?
BFS explores all neighbors before moving deeper, while DFS dives deep into one branch before backtracking.
Q4: Can BFS be used to find the shortest path?
Yes, BFS is ideal for finding the shortest path in an unweighted graph.
Q5: Is BFS applicable to both directed and undirected graphs?
Yes, BFS can be used on both types of graphs with minor modifications.
Conclusion
Breadth-First Search is a foundational algorithm that every programmer should understand. It forms the basis for many complex algorithms and is widely used in networking, pathfinding, and artificial intelligence. Through these five Java programs, we’ve seen how BFS can be implemented using queues, matrices, recursion, and user input, and even applied to find the shortest path.
For beginners, practicing these examples is the best way to build confidence. Try modifying the code, adding more nodes, or changing the graph structure to see how BFS responds. With a strong grasp of BFS, you’ll find it much easier to understand other advanced graph algorithms in the future.
