This is a Java Program to implment graph and check the connectivity between nodes using a standard Breadth First Search algorithm. Algorithm visits the node that was traversed first or appeared in liked list representation of the node or first come first serve basis. We create a vistied array to avoid revisiting a node. If destination node appears in visited array, source and destination nodes are connected, not otherwise.
Here is the source code of the Java Program to Check the Connectivity of Graph Using BFS. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to check the nodes are connected using BFS import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Connectivity_BFS { private final int vertices; private int[][] adjacency_matrix; private Queue<Integer> queue; public Connectivity_BFS(int v) { vertices = v; adjacency_matrix = new int[vertices + 1][vertices + 1]; queue = new LinkedList<Integer>(); } public void makeEdge(int to, int from, int edge) { try { adjacency_matrix[to][from] = edge; adjacency_matrix[from][to] = edge; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } } public int getEdge(int to, int from) { try { return adjacency_matrix[to][from]; } catch (ArrayIndexOutOfBoundsException index) { System.out.println("The vertices does not exists"); } return -1; } public void bfs(int source) { int number_of_nodes = adjacency_matrix.length - 1; int[] visited = new int[number_of_nodes + 1]; int i, element; visited = 1; queue.add(source); while (!queue.isEmpty()) { element = queue.remove(); i = 1;// element; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } System.out.print("The source node " + source + " is connected to: "); int count = 0; for (int v = 1; v <= number_of_nodes; v++) if (visited[v] == 1) { System.out.print(v + " "); count++; } if (count == number_of_nodes) System.out.print("\nThe Graph is Connected "); else System.out.print("\nThe Graph is Disconnected "); } public static void main(String args[]) { int v, e, count = 1, to = 0, from = 0; Scanner sc = new Scanner(System.in); Connectivity_BFS graph; System.out.println("The Undirected Graph Connectivity Test"); try { System.out.println("Enter the number of vertices: "); v = sc.nextInt(); System.out.println("Enter the number of edges: "); e = sc.nextInt(); graph = new Connectivity_BFS(v); System.out.println("Enter the edges: <to> <from>"); while (count <= e) { to = sc.nextInt(); from = sc.nextInt(); graph.makeEdge(to, from, 1); count++; } System.out.println("The adjacency matrix for the given graph is: "); System.out.print(" "); for (int i = 1; i <= v; i++) System.out.print(i + " "); System.out.println(); for (int i = 1; i <= v; i++) { System.out.print(i + " "); for (int j = 1; j <= v; j++) System.out.print(graph.getEdge(i, j) + " "); System.out.println(); } System.out.println("Enter the Source Node: "); int sourceNode = sc.nextInt(); graph.bfs(sourceNode); } catch (Exception E) { System.out.println("Something went wrong"); } sc.close(); } }
Output:
$ javac Connectivity_BFS.java $ java Connectivity_BFS The Undirected Graph Connectivity Test(BFS) Enter the number of vertices: 4 Enter the number of edges: 2 Enter the edges: <to> <from> 1 2 3 4 The adjacency matrix for the given graph is: 1 2 3 4 1 0 1 0 0 2 1 0 0 0 3 0 0 0 1 4 0 0 1 0 Enter the Source Node: 3 The source node 3 is connected to: 3 4 The Graph is Disconnected The Undirected Graph Connectivity Test(BFS) Enter the number of vertices: 4 Enter the number of edges: 5 Enter the edges: <to> <from> 1 2 2 3 3 4 1 4 1 3 The adjacency matrix for the given graph is: 1 2 3 4 1 0 1 1 1 2 1 0 1 0 3 1 1 0 1 4 1 0 1 0 Enter the Source Node: 4 The source node 4 is connected to: 1 2 3 4 The Graph is Connected
Related posts:
Introduction to Spring Data REST
Using Optional with Jackson
Java Program to Find Minimum Element in an Array using Linear Search
Using a Spring Cloud App Starter
Prevent Brute Force Authentication Attempts with Spring Security
Hướng dẫn Java Design Pattern – Bridge
Từ khóa throw và throws trong Java
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
HttpClient 4 Cookbook
OAuth 2.0 Resource Server With Spring Security 5
Hướng dẫn Java Design Pattern – Iterator
So sánh ArrayList và LinkedList trong Java
Overview of the java.util.concurrent
Java Program to Compute the Area of a Triangle Using Determinants
What is Thread-Safety and How to Achieve it?
Introduction to Thread Pools in Java
Enum trong java
Java Program to Implement Max-Flow Min-Cut Theorem
Introduction to Using Thymeleaf in Spring
Spring Cloud Series – The Gateway Pattern
Java Program to Implement Hash Tables
Spring Boot - OAuth2 with JWT
Java CyclicBarrier vs CountDownLatch
A Guide to Iterator in Java
Dockerizing a Spring Boot Application
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
An Intro to Spring Cloud Security
Java Program to Implement Depth-limited Search
Quick Guide to java.lang.System
Java 8 StringJoiner
Spring Cloud Bus
Sử dụng Fork/Join Framework với ForkJoinPool trong Java