This Java program is to check whether graph is Biconnected. In graph theory, a biconnected graph is a connected and “nonseparable” graph, meaning that if any vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
Here is the source code of the Java program to check whether graph is biconnected. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.HashSet; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; import java.util.Stack; public class BiconnectedGraph { private Queue<Integer> queue; private Stack<Integer> stack; private int numberOfNodes; private Set<Integer> articulationPoints; private int[] parent; private int[] visited; private int[][] adjacencyMatrix; public BiconnectedGraph(int numberOfNodes) { queue = new LinkedList<Integer>(); this.numberOfNodes = numberOfNodes; this.stack = new Stack<Integer>(); this.articulationPoints = new HashSet<Integer>(); this.parent = new int[numberOfNodes + 1]; this.visited = new int[numberOfNodes + 1]; this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1]; } private boolean bfs(int adjacency_matrix[][], int source) { boolean connected = true; 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 = element; while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } for (int vertex = 1; vertex <= number_of_nodes; vertex++) { if (visited[vertex] == 1) { continue; }else { connected = false; break; } } return connected; } private int numberOfArticulationPoint(int adjacencyMatrix[][], int source) { int children = 0; int element, destination; stack.push(source); visited = 1; for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++) { this.adjacencyMatrix[sourceVertex][destinationVertex] = adjacencyMatrix[sourceVertex][destinationVertex]; } } while (!stack.isEmpty()) { element = stack.peek(); destination = element; while (destination <= numberOfNodes) { if (this.adjacencyMatrix[element][destination] == 1 && visited[destination] == 0) { stack.push(destination); visited[destination] = 1; parent[destination] = element; if (element == source) { children++; } if (!isLeaf(this.adjacencyMatrix, destination)) { if (children > 1) { articulationPoints.add(source); } if(isArticulationPoint(this.adjacencyMatrix, destination)) { articulationPoints.add(destination); } } element = destination; destination = 1; continue; } destination++; } stack.pop(); } return articulationPoints.size(); } public boolean isArticulationPoint(int adjacencyMatrix[][], int root) { int explored[] = new int[numberOfNodes + 1]; Stack<Integer> stack = new Stack<Integer>(); stack.push(root); int element = 0,destination = 0; while(!stack.isEmpty()) { element = stack.peek(); destination = 1; while (destination <= numberOfNodes) { if ( element != root) { if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1) { if (this.stack.contains(destination)) { if (destination <= parent[root]) { return false; } return true; } } } if ((adjacencyMatrix[element][destination] == 1 && explored[destination] == 0 ) && visited[destination] == 0) { stack.push(destination); explored[destination] = 1; adjacencyMatrix[destination][element] = 0; element = destination; destination = 1; continue; } destination++; } stack.pop(); } return true; } private boolean isLeaf(int adjacencyMatrix[][], int node) { boolean isLeaf = true; for (int vertex = 1; vertex <= numberOfNodes; vertex++) { if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 1) { isLeaf = true; }else if (adjacencyMatrix[node][vertex] == 1 && visited[vertex] == 0) { isLeaf = false; break; } } return isLeaf; } public boolean isBiconnected(int adjacencyMatrix[][], int source) { boolean biconnected = false; if (bfs(adjacencyMatrix, source) && numberOfArticulationPoint(adjacencyMatrix, source) == 0) { biconnected = true; } return biconnected; } public static void main(String... arg) { int number_of_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_of_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_of_nodes; i++) for (int j = 1; j <= number_of_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); BiconnectedGraph biconnectedGraph = new BiconnectedGraph(number_of_nodes); if (biconnectedGraph.isBiconnected(adjacency_matrix, source)) { System.out.println("The Given Graph is BiConnected"); }else { System.out.println("The Given Graph is Not BiConnected"); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
$javac BiConnectedGraph.java $java BiConnectedGraph Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Enter the source for the graph 1 The Given Graph is BiConnected
Related posts:
Removing all Nulls from a List in Java
Updating your Password
How to Read HTTP Headers in Spring REST Controllers
Java Program to Implement Hash Tables with Quadratic Probing
Performance Difference Between save() and saveAll() in Spring Data
Java Program to implement Circular Buffer
Rate Limiting in Spring Cloud Netflix Zuul
Constructor Dependency Injection in Spring
Java Program to Check the Connectivity of Graph Using BFS
Java Program to Implement Binomial Tree
A Guide to Spring Cloud Netflix – Hystrix
Java Program to Implement Park-Miller Random Number Generation Algorithm
Java Program to Implement Hash Tree
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Spring Boot - OAuth2 with JWT
Java Program to Implement HashTable API
Supplier trong Java 8
Java Program to Check for balanced parenthesis by using Stacks
Spring @RequestParam Annotation
Using JWT with Spring Security OAuth
Custom Thread Pools In Java 8 Parallel Streams
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Adding a Newline Character to a String in Java
Read an Outlook MSG file
Using Spring ResponseEntity to Manipulate the HTTP Response
MyBatis with Spring
Java Program to implement Priority Queue
Vòng lặp for, while, do-while trong Java
Java Program to Implement Hash Tables Chaining with Binary Trees
Posting with HttpClient
Logout in an OAuth Secured Application
Java Program to Implement Levenshtein Distance Computing Algorithm