This is the Java Program to do a Breadth First Search/Traversal on a graph non-recursively.

Given a graph in the form of an adjacency matrix and a source vertex, write a program to perform a breadth-first search of the graph. In breadth-first search traversal, nodes are traversed level by level.

The idea is to **store the source vertex in the queue**. Now, iterate through the queue until it is empty. For every vertex retrieved from the queue, check which of its neighbours are still not processed. Add those neighbours to the queue.

Here is the source code of the Java Program to do a Breadth First Search/Traversal on a graph non-recursively. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

`//Java Program to do a Breadth First Search/Traversal on a graph non-recursively`

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class BreadthFirstSearch {

`// Function to perform breadth first search`

static void breadthFirstSearch(int[][] matrix, int source){

boolean[] visited = new boolean[matrix.length];

visited[source-1] = true;

Queue<Integer> queue = new LinkedList<>();

queue.add(source);

System.out.println("The breadth first order is");

while(!queue.isEmpty()){

System.out.println(queue.peek());

int x = queue.poll();

int i;

for(i=0; i<matrix.length;i++){

if(matrix[x-1][i] == 1 && visited[i] == false){

queue.add(i+1);

visited[i] = true;

`}`

`}`

`}`

`}`

`// Function to read user input`

public static void main(String[] args) {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int vertices;

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

try{

vertices = Integer.parseInt(br.readLine());

}catch(IOException e){

System.out.println("An error occurred");

return;

`}`

int[][] matrix = new int[vertices][vertices];

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

int i,j;

for(i=0; i<vertices; i++){

for(j=0; j<vertices; j++){

try{

matrix[i][j] = Integer.parseInt(br.readLine());

}catch (IOException e){

System.out.println("An error occurred");

`}`

`}`

`}`

int source;

System.out.println("Enter the source vertex");

try{

source = Integer.parseInt(br.readLine());

}catch(IOException e){

System.out.println("An error occurred");

return;

`}`

breadthFirstSearch(matrix,source);

`}`

`}`

1. In function breadthFirstSearch(), a boolean array is created and visited value of the source is set to true.

2. Then a queue is created and source vertex is added to it.

3. The loop while(!queue.isEmpty()) traverses until the queue is empty.

4. The nested loop for(i=0; i<matrix.length; i++) traverses through all the neighbours of the currently polled vertex from the queue.

5. The condition if(matrix[x-1][i] == 1 && visited[i] == false) looks for all the neighbours of the currently polled vertex and adds the non-visited vertices to the queue.

**Time Complexity: O(n ^{2})** where n is the number of elements in the array.

Case 1 (Simple Test Case): Enter the number of vertices in the graph 4 Enter the adjacency matrix 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 1 Enter the source vertex 3 The breadth first order is 3 1 2 Case 2 (Simple Test Case - another example): Enter the number of vertices in the graph 3 Enter the adjacency matrix 0 0 0 1 0 1 1 1 1 Enter the source vertex 2 The breadth first order is 2 1 3

**Sanfoundry Global Education & Learning Series – Java Programs.**

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Java Books
- Apply for Computer Science Internship
- Check Programming Books
- Practice Information Technology MCQs
- Practice Programming MCQs