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:
Phân biệt JVM, JRE, JDK
Registration with Spring Security – Password Encoding
Spring Security and OpenID Connect
ETags for REST with Spring
Phương thức tham chiếu trong Java 8 – Method References
Spring Boot - Web Socket
Using Custom Banners in Spring Boot
Jackson Date
Chuyển đổi từ HashMap sang ArrayList
Most commonly used String methods in Java
Java Program to Implement Shell Sort
Guide to ThreadLocalRandom in Java
Java Program to Implement VList
Spring Cloud – Bootstrapping
Hướng dẫn sử dụng Java Annotation
Spring Boot - Google Cloud Platform
How to Read HTTP Headers in Spring REST Controllers
Configure a Spring Boot Web Application
Introduction to Liquibase Rollback
Apache Commons Collections BidiMap
Spring Security Custom AuthenticationFailureHandler
Java Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers
Dockerizing a Spring Boot Application
Java Program to Implement the Checksum Method for Small String Messages and Detect
Java Program to Implement ArrayDeque API
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Introduction to Using FreeMarker in Spring MVC
Check if there is mail waiting
Check If a String Is Numeric in Java
A Guide to Spring Boot Admin
Java String Conversions
Java Program to Implement Counting Sort