Breadth first search java source code

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

Problem Description
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.

Problem Solution
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.

Program/Source Code
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 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