import java.util.InputMismatchException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BFS { private Queue queue; public BFS() { queue = new LinkedList(); } 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; visited[source] = 1; queue.add(source); while (!queue.isEmpty()) { element = queue.remove(); i = element; System.out.print(i + "\t"); while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } } 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(); } } /* Enter the number of nodes in the graph 4 Enter the adjacency matrix 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 Enter the source for the graph 1 The BFS traversal of the graph is 1 2 4 3