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 implement Associate Array
Java Program to find the number of occurrences of a given number using Binary Search approach
Spring Boot Configuration with Jasypt
Guide to System.gc()
Spring Security Custom AuthenticationFailureHandler
Implementing a Binary Tree in Java
Java Program to Implement LinkedBlockingDeque API
JUnit 5 @Test Annotation
Lớp Properties trong java
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Spring Boot - Servlet Filter
@Lookup Annotation in Spring
Custom Thread Pools In Java 8 Parallel Streams
Java Program to Implement Adjacency Matrix
Java Program to Implement Binomial Tree
Java 8 and Infinite Streams
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Program to Implement Lloyd’s Algorithm
Spring Boot - Web Socket
Functional Interfaces in Java 8
Spring Boot - Logging
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Implement LinkedHashMap API
Quick Guide to Spring Controllers
Java Program to Solve a Matching Problem for a Given Specific Case
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
How to Replace Many if Statements in Java
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java Program to Implement Red Black Tree
OAuth2.0 and Dynamic Client Registration
Summing Numbers with Java Streams
Java Program to Implement Disjoint Set Data Structure