Implementing BFS in Java

Ankur Aug 28, 2015 5 min read

In this post, we implement Breadth-First Search (BFS) in Java using an adjacency matrix. BFS is a fundamental graph traversal algorithm that visits all nodes level by level, starting from a source node and exploring all its direct neighbours before moving deeper into the graph. It is widely used in shortest path problems, network analysis, and AI search strategies.

What is BFS?

BFS explores a graph by using a queue data structure. It starts at a chosen node (node 1 in our implementation), adds it to the queue, and then repeatedly dequeues a node, visits all its unvisited neighbours, and enqueues them. This guarantees that all nodes at depth d are visited before any node at depth d+1.

The graph in this implementation is represented as an adjacency matrix — a 2D array where m[i][j] = 1 means there is an edge between node i+1 and node j+1, and 0 means no edge.

Java Code Implementation

// ============================================================
// Breadth-First Search (BFS) in Java
// Graph is represented as an adjacency matrix.
// BFS visits nodes level by level using a queue.
// ============================================================

import java.io.*;
import java.util.*;

public class BFSDemo {

    // Adjacency matrix — m[i][j] = 1 means an edge exists between node i+1 and j+1
    static int[][] m = new int[50][50];
    static int n;                  // Number of nodes in the graph

    public static void main(String[] args) 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 (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                m[i][j] = Integer.parseInt(obj.readLine());
            }
        }

        // ----- PRINT ENTERED MATRIX -----
        System.out.println("\nEntered adjacency matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(m[i][j] + " ");
            }
            System.out.println();
        }

        // ----- BFS TRAVERSAL -----
        int[] q = new int[100];  // Queue to store the BFS traversal order
        q[0] = 1;                // Start BFS from node 1 (1-indexed)
        int qpos = 1;            // Current size of the queue
        int i = 0;               // Index of the node being processed

        while (i < qpos) {
            // For each unvisited neighbour of node q[i]
            for (int j = i; j < n; j++) {
                if (m[i][j] != 0) {         // Edge exists between current node and j+1

                    // Check if node j+1 is already in the queue (visited)
                    int l = 0;              // Flag: 0 = not visited, 1 = already visited
                    for (int k = 0; k < qpos; k++) {
                        if (q[k] == j + 1) {
                            l = 1;          // Node j+1 already in traversal
                        }
                    }

                    if (l == 0) {           // Not visited yet — add to queue
                        q[qpos] = j + 1;
                        qpos++;
                    }
                }
            }
            i++;  // Move to next node in the queue
        }

        // ----- OUTPUT -----
        System.out.println("\nBFS Traversal Order:");
        for (int j = 0; j < qpos; j++) {
            System.out.print(q[j] + " ");
        }
        System.out.println();
    }
}

Explanation of the Code

Adjacency Matrix Input — The user enters the number of nodes n and then fills the n × n adjacency matrix one value at a time. A value of 1 at position [i][j] means nodes i+1 and j+1 are connected.
Queue Array — Instead of Java’s built-in Queue, we use a plain integer array q[] as a simple queue. The variable qpos tracks how many nodes have been enqueued, and i tracks which node is currently being processed.
Visited Check — Before adding a neighbour to the queue, we scan the existing queue to see if the node is already present. If it is, we skip it (flag l=1). This prevents visiting the same node twice.
Level-by-Level Traversal — The outer while (i < qpos) loop processes each node in the queue. For every node, we find all its neighbours in the matrix and add unvisited ones. This naturally produces a BFS (level-order) traversal.

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 input represents an 8-node undirected graph. Node 1 is connected to nodes 2, 3, and 4. Node 2 is connected to nodes 5 and 6. Node 4 is connected to nodes 7 and 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

BFS Traversal Order:
1 2 3 4 5 6 7 8

Step-by-Step Output Explanation

Start: Node 1 is placed in the queue. Queue = [1].
Process Node 1: Neighbours are 2, 3, 4 — all unvisited. Queue = [1, 2, 3, 4].
Process Node 2: Neighbours are 1 (visited), 5, 6. Add 5, 6. Queue = [1, 2, 3, 4, 5, 6].
Process Node 3: Neighbour is 1 (visited). Nothing added.
Process Node 4: Neighbours are 1 (visited), 7, 8. Add 7, 8. Queue = [1, 2, 3, 4, 5, 6, 7, 8].
Nodes 5–8: All their neighbours are already visited. Nothing new added.
Final output: 1 2 3 4 5 6 7 8 — a clean level-order traversal of the graph.

Conclusion

BFS is a reliable and intuitive graph traversal algorithm guaranteed to visit nodes in shortest-path order for unweighted graphs. This adjacency matrix implementation works well for small, dense graphs and is a great starting point for understanding graph algorithms. For sparse or large graphs, an adjacency list representation would be more memory-efficient. Once you are comfortable with BFS, a natural next step is to explore Depth-First Search (DFS), which uses a stack instead of a queue and explores as deep as possible before backtracking.

Java

One Reply to “Implementing BFS in Java”

Husain Aug 5th at 8:29 pm

How to calculate space and time complexity of BFS in program ?

Reply