1. Introduction

Breadth-First Search (BFS) is one of the simplest algorithms for searching a graph. It traverses the graph layer by layer, visiting all nodes at the current depth before moving to nodes at the next depth level. In this blog post, we’ll implement the BFS algorithm to traverse a graph using an adjacency list representation in Java.

2. Program Steps

1. Define the Graph class with a list of linked lists to represent the adjacency list.

2. Implement methods to add nodes, add edges, and perform BFS.

3. Test the BFS traversal using a main class.

3. Code Program

import java.util.LinkedList;
import java.util.Queue;

class Graph {
    private final int numVertices;
    private final LinkedList<Integer>[] adjacencyList;

    // Constructor
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // Add edge to the graph
    public void addEdge(int src, int dest) {
        adjacencyList[src].add(dest);
    }

    // Perform BFS and print nodes in BFS order
    public void BFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

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

            for (int i : adjacencyList[vertex]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        System.out.print("Breadth-First Search starting from vertex 0:");
        graph.BFS(0);
    }
}

Output:

Breadth-First Search starting from vertex 0: 0 1 2 3 4

4. Step By Step Explanation

1. We initialize our Graph class containing an array of LinkedLists. This array will store the adjacency list for each vertex of the graph.

2. We use a constructor to initialize the adjacency list for all vertices.

3. The addEdge method allows us to add an edge between two vertices by adding each vertex to the adjacency list of the other.

4. The BFS method is the core of our program. It starts from the given startVertex and traverses the graph in a breadth-first manner. We use a queue to keep track of nodes yet to be explored and an array to mark visited nodes. The method prints the vertices in BFS order.

5. In the main method, we set up a sample graph and initiate a BFS traversal starting from vertex 0.

6. The output demonstrates the BFS traversal order of the nodes in the graph.