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:
Tạo chương trình Java đầu tiên sử dụng Eclipse
Custom HTTP Header with the HttpClient
Java Program to Implement RoleList API
Tính đóng gói (Encapsulation) trong java
Spring Security Authentication Provider
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Java – InputStream to Reader
Hướng dẫn Java Design Pattern – State
Adding a Newline Character to a String in Java
Logout in an OAuth Secured Application
Java Program to Represent Graph Using Incidence Matrix
Java Program to Implement Binary Tree
Quick Guide to the Java StringTokenizer
Java Byte Array to InputStream
Spring Security Basic Authentication
Write/Read cookies using HTTP and Read a file from the internet
Composition, Aggregation, and Association in Java
Java Program to implement Bit Set
Java Program to Perform Left Rotation on a Binary Search Tree
Marker Interface trong Java
Phương thức tham chiếu trong Java 8 – Method References
Java Program to Implement Hash Tables chaining with Singly Linked Lists
Logging a Reactive Sequence
Java Program to Implement DelayQueue API
Using the Not Operator in If Conditions in Java
Hướng dẫn Java Design Pattern – Facade
Java Program to Find the Edge Connectivity of a Graph
Java Program to Implement Tarjan Algorithm
Java Program to Implement Ford–Fulkerson Algorithm
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Ways to Iterate Over a List in Java
Introduction to Spring Data MongoDB