This Java program demonstrates how to perform Breadth-First Search (BFS) traversal in a graph. BFS is used for searching a graph in a layer-wise manner, which helps in finding the shortest path in an unweighted graph.

Java Code

import java.util.*;

class Graph {
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency lists

    // Constructor
    Graph(int V) {
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < V; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // Function to add an edge into the graph
    void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's list.
    }

    // Prints BFS traversal from a given source s
    void BFS(int s) {
        // Mark all the vertices as not visited(By default set as false)
        boolean visited[] = new boolean[V];

        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s + " ");

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

public class BFSDemo {
    public static void main(String[] args) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal " +
                           "(starting from vertex 2)");

        g.BFS(2);
    }
}

Explanation of the Code

The program includes:

• Graph Class: This class handles the graph representation and operations. The graph is represented using an adjacency list.
• addEdge Method: Adds a directed edge from vertex ‘v’ to vertex ‘w’.
• BFS Method: Implements the BFS traversal from a given source node. This method uses a queue to handle the layer-by-layer exploration of the graph.

This BFS implementation is essential for algorithms that need to explore levels of depth in fields such as networking, pathfinding in games, and many areas of research.