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

Here is the source code of the Java program to check the connectivity of the undirected graph using BFS. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

import java.util.InputMismatchException;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class UndirectedConnectivityBFS

`{`

private Queue<Integer> queue;

public UndirectedConnectivityBFS()

`{`

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;

visited[source] = 1;

queue.add(source);

while (!queue.isEmpty())

`{`

element = queue.remove();

i = element;

while (i <= number_of_nodes)

`{`

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

`{`

queue.add(i);

visited[i] = 1;

`}`

`i++;`

`}`

`}`

boolean connected = false;

for (int vertex = 1; vertex <= number_of_nodes; vertex++)

`{`

if (visited[vertex] == 1)

`{`

connected = true;

} else

`{`

connected = false;

break;

`}`

`}`

if (connected)

`{`

System.out.println("The graph is connected");

} else

`{`

System.out.println("The graph is disconnected");

`}`

`}`

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();

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

`{`

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

`{`

if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)

`{`

adjacency_matrix[j][i] = 1;

`}`

`}`

`}`

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

source = scanner.nextInt();

UndirectedConnectivityBFS undirectedConnectivity= new UndirectedConnectivityBFS();

undirectedConnectivity.bfs(adjacency_matrix, source);

} catch (InputMismatchException inputMismatch)

`{`

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

`}`

scanner.close();

`}`

`}`

$javac UndirectedConnectivityBFS.java $java UndirectedConnectivityBFS Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Enter the source for the graph 1 The graph is disconnected

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

advertisement

advertisement

If you wish to look at all Java Programming examples, go to Java Programs.

**Related Posts:**

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