Breadth First Search

Breadth First Search (BFS): is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Fringe is a FIFO queue.

This Java program, to perform the bfs traversal of a given graph in the form of the adjacency matrix.the bfs traversal makes use of a queue.

Here is the source code of the Java program to perform the BFS traversal. The Java program is successfully compiled and run on a Linux system and Windows also.

package uninformed;

/**

 *

 * @author sam

 */

import java.util.InputMismatchException;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class BFS

{ 

    private Queue<Integer> queue;

    public BFS()

    {

        queue = new LinkedList<Integer>();

    }

    public void bfs(int adjacency_matrix[][], int source)

    {

        int number_of_nodes = adjacency_matrix[source].length - 1;

        

        

        

        int[] visited = new int[number_of_nodes + 1];

        int i, element, goalnode;

        Scanner scanner = new Scanner(System.in);

        System.out.print("ENTER THE GOAL NODE: ");

        goalnode = scanner.nextInt();

        visited[source] = 1;

        queue.add(source);

        while (!queue.isEmpty())

        {

            element = queue.remove();

            i = element;

            

            System.out.print(i + "\t");

            if(i == goalnode) return;

            while (i <= number_of_nodes)

            {

                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)

                {

                    queue.add(i);

                    visited[i] = 1;

                }

                i++;

            }

        }

        System.out.println();

    }

    public static void main(String... arg)

    {

        int number_no_nodes, source;

        Scanner scanner = null;

        try

        {

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_no_nodes = scanner.nextInt();

            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];

            System.out.println("Enter the adjacency matrix");

            for (int i = 1; i <= number_no_nodes; i++)

                for (int j = 1; j <= number_no_nodes; j++)

                    adjacency_matrix[i][j] = scanner.nextInt();

            System.out.println("Enter the source for the graph");

            source = scanner.nextInt();

            System.out.println("The BFS traversal of the graph is ");

            BFS bfs = new BFS();

            bfs.bfs(adjacency_matrix, source);

        } catch (InputMismatchException inputMismatch)

        {

            System.out.println("Wrong Input Format");

        }

        scanner.close();

    }

}