1. Introduction

Breadth-First Search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order i.e. it visits all the vertices at the same depth before moving to the next level.

2. Program Steps

1. Start from the source vertex.

2. Visit the adjacent unvisited vertex, mark it as visited, and enqueue it into a queue.

3. If no adjacent vertex is found, dequeue the next vertex from the queue.

4. Repeat steps 2 and 3 until the queue is empty.

3. Code Program

import java.util.*;

public class BFS {

    private int V;   // No. of vertices
    private LinkedList<Integer> adjList[]; //Adjacency Lists

    // Constructor
    BFS(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adjList[i] = new LinkedList();
        }
    }

    // Function to add an edge into the graph
    void addEdge(int v,int w) {
        adjList[v].add(w);
    }

    // BFS traversal from a given source s
    void traverse(int s) {
        boolean visited[] = new boolean[V];

        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited[s]=true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s+" ");

            Iterator<Integer> i = adjList[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        BFS g = new BFS(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("Breadth First Traversal starting from vertex 2:");

        g.traverse(2);
    }
}

Output:

Breadth First Traversal starting from vertex 2:
2 0 3 1

4. Step By Step Explanation

1. BFS: Main class that represents a directed graph using adjacency list representation.

2. BFS(int v): Constructor to initialize the graph with the specified number of vertices.

3. addEdge(int v, int w): Function to add an edge to the graph.

4. traverse(int s): This method implements the BFS traversal. It takes a source node s and visits all nodes reachable from s using BFS.

5. Inside the traverse method, a boolean array visited is used to keep track of visited vertices. A queue is used to achieve BFS traversal.

6. We mark the source node as visited and enqueue it. Then, while the queue is not empty, we dequeue a vertex, print it, and enqueue all its unvisited neighbors.

7. This process ensures all nodes at the current depth (distance from the source node) are visited before moving to the next depth.

8. The main method creates a graph, adds edges, and then calls the traverse method to print the BFS traversal starting from vertex 2.

The time complexity of the BFS algorithm is O(V+E) where V is the number of vertices in the graph and E is the number of edges.