Java Program to Implement BFS (Breadth-First Search)

A Java program to implement BFS uses a Queue to explore nodes level by level starting from a source node, like: Queue queue = new LinkedList<>(); queue.add(startNode); while(!queue.isEmpty()) { int node = queue.poll(); /* process node */ }.

Examples

InputGraph edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

OutputBFS traversal starting from node 2: 2 0 3 1

InputGraph edges: 1-2, 1-3, 2-4, 3-4; Start node: 1

OutputBFS traversal starting from node 1: 1 2 3 4

InputGraph edges: 0-1; Start node: 0

OutputBFS traversal starting from node 0: 0 1

How to Think About It

To implement BFS, think of visiting nodes in layers starting from the start node. Use a queue to keep track of nodes to visit next. Mark nodes as visited when you add them to the queue to avoid repeats. Keep removing nodes from the queue, process them, and add their unvisited neighbors until no nodes remain.

Algorithm

1

Create a queue and add the start node to it.

2

Mark the start node as visited.

3

While the queue is not empty, do:

4

Remove the front node from the queue and process it.

5

Add all unvisited neighbors of this node to the queue and mark them visited.

6

Repeat until the queue is empty.

Code

java

import java.util.*;

public class BFS {
    private int vertices;
    private LinkedList<Integer>[] adjList;

    public BFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : adjList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS graph = new BFS(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.print("BFS traversal starting from node 2: ");
        graph.bfs(2);
    }
}

Output

BFS traversal starting from node 2: 2 0 3 1 

Dry Run

Let's trace BFS starting from node 2 on the example graph.

1

Initialize

visited = [false, false, false, false], queue = []

2

Start from node 2

visited = [false, false, true, false], queue = [2]

3

Process node 2

Print 2; neighbors = [0, 3]; add unvisited neighbors 0 and 3 visited = [true, false, true, true], queue = [0, 3]

4

Process node 0

Print 0; neighbors = [1, 2]; add unvisited neighbor 1 visited = [true, true, true, true], queue = [3, 1]

5

Process node 3

Print 3; neighbors = [3]; already visited, no addition queue = [1]

6

Process node 1

Print 1; neighbors = [2]; already visited, no addition queue = []

Queue	Visited	Output
[2]	[false, false, true, false]
[0, 3]	[true, false, true, true]	2
[3, 1]	[true, true, true, true]	2 0
[1]	[true, true, true, true]	2 0 3
[]	[true, true, true, true]	2 0 3 1

Why This Works

Step 1: Use a queue to explore nodes

The queue ensures nodes are processed in the order they are discovered, which is key to BFS visiting nodes level by level.

Step 2: Mark nodes visited when added

Marking nodes as visited when adding to the queue prevents revisiting and infinite loops.

Step 3: Process neighbors of each node

For each node removed from the queue, add all unvisited neighbors to the queue to explore them next.

Alternative Approaches

Recursive BFS using helper function

java

import java.util.*;

public class RecursiveBFS {
    private int vertices;
    private LinkedList<Integer>[] adjList;

    public RecursiveBFS(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);
        bfsHelper(queue, visited);
    }

    private void bfsHelper(Queue<Integer> queue, boolean[] visited) {
        if (queue.isEmpty()) return;
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
        bfsHelper(queue, visited);
    }

    public static void main(String[] args) {
        RecursiveBFS graph = new RecursiveBFS(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.print("Recursive BFS starting from node 2: ");
        graph.bfs(2);
    }
}

Uses recursion to process the queue, which can be less efficient and risk stack overflow on large graphs.

BFS using adjacency matrix

java

import java.util.*;

public class BFSMatrix {
    private int vertices;
    private int[][] adjMatrix;

    public BFSMatrix(int v) {
        vertices = v;
        adjMatrix = new int[v][v];
    }

    public void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
    }

    public void bfs(int start) {
        boolean[] visited = new boolean[vertices];
        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 < vertices; i++) {
                if (adjMatrix[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFSMatrix graph = new BFSMatrix(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.print("BFS traversal using adjacency matrix from node 2: ");
        graph.bfs(2);
    }
}

Uses adjacency matrix which can be simpler but uses more memory for large sparse graphs.

Complexity: O(V + E) time, O(V) space

Time Complexity

BFS visits every vertex and edge once, so the time is proportional to the number of vertices plus edges, O(V + E).

Space Complexity

The queue and visited array use space proportional to the number of vertices, O(V).

Which Approach is Fastest?

Using adjacency lists is faster and more memory efficient for sparse graphs compared to adjacency matrices.

Approach	Time	Space	Best For
Adjacency List BFS	O(V + E)	O(V)	Sparse graphs, memory efficient
Adjacency Matrix BFS	O(V^2)	O(V^2)	Dense graphs, simple implementation
Recursive BFS	O(V + E)	O(V) + call stack	Small graphs, educational use