This is a Java Program to Implement Warshall Transitive closure Algorithm. Warshall’s Transitive closure algorithm is used to determine if a path exists from vertex a to vertex b for all vertex pairs (a, b) in a graph.
Here is the source code of the Java Program to Implement Warshall Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Warshall Algorithm **/ import java.util.Scanner; /** Class Warshall **/ public class Warshall { private int V; private boolean[][] tc; /** Function to make the transitive closure **/ public void getTC(int[][] graph) { this.V = graph.length; tc = new boolean[V][V]; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) if (graph[i][j] != 0) tc[i][j] = true; tc[i][i] = true; } for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (tc[j][i]) for (int k = 0; k < V; k++) if (tc[j][i] && tc[i][k]) tc[j][k] = true; } } } /** Funtion to display the trasitive closure **/ public void displayTC() { System.out.println("\nTransitive closure :\n"); System.out.print(" "); for (int v = 0; v < V; v++) System.out.print(" " + v ); System.out.println(); for (int v = 0; v < V; v++) { System.out.print(v +" "); for (int w = 0; w < V; w++) { if (tc[v][w]) System.out.print(" * "); else System.out.print(" "); } System.out.println(); } } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Warshall Algorithm Test\n"); /** Make an object of Warshall class **/ Warshall w = new Warshall(); /** Accept number of vertices **/ System.out.println("Enter number of vertices\n"); int V = scan.nextInt(); /** get graph **/ System.out.println("\nEnter matrix\n"); int[][] graph = new int[V][V]; for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) graph[i][j] = scan.nextInt(); w.getTC(graph); w.displayTC(); } }
Warshall Algorithm Test Enter number of vertices 6 Enter matrix 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 Transitive closure : 0 1 2 3 4 5 0 * * * * * 1 * 2 * * * * * * 3 * 4 * * 5 * * *
Related posts:
Java Program to Find All Pairs Shortest Path
Quick Guide to java.lang.System
How to Add a Single Element to a Stream
Java Program to Find Basis and Dimension of a Matrix
Java Program to Perform Deletion in a BST
Quick Guide on Loading Initial Data with Spring Boot
Tìm hiểu về Web Service
Java Program to Implement Levenshtein Distance Computing Algorithm
Java Program to Implement JobStateReasons API
HttpClient Connection Management
Java – Convert File to InputStream
Java 8 Predicate Chain
Period and Duration in Java
String Processing with Apache Commons Lang 3
Converting Between an Array and a Set in Java
Spring Boot - Thymeleaf
Java Program to Implement Disjoint Sets
Auditing with JPA, Hibernate, and Spring Data JPA
Java Program to Implement Graph Structured Stack
Spring Data JPA @Query
Java Program to Generate Random Numbers Using Probability Distribution Function
Giới thiệu java.io.tmpdir
The DAO with Spring and Hibernate
Spring Boot - Application Properties
The Spring @Controller and @RestController Annotations
ExecutorService – Waiting for Threads to Finish
Generate Spring Boot REST Client with Swagger
Registration – Password Strength and Rules
Testing an OAuth Secured API with Spring MVC
Jackson Annotation Examples
An Intro to Spring Cloud Security
The Dining Philosophers Problem in Java