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:
Guide to the Synchronized Keyword in Java
Java Program to Implement Red Black Tree
Serialize Only Fields that meet a Custom Criteria with Jackson
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Lớp lồng nhau trong java (Java inner class)
Immutable Map Implementations in Java
Java Program to Create a Balanced Binary Tree of the Incoming Data
Allow user:password in URL
Spring MVC Content Negotiation
Spring Boot - Code Structure
Java Program to Implement TreeSet API
Đồng bộ hóa các luồng trong Java
Java Program to Solve the 0-1 Knapsack Problem
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Java Program to Implement Extended Euclid Algorithm
“Stream has already been operated upon or closed” Exception in Java
Java Program to Search for an Element in a Binary Search Tree
Introduction to Thread Pools in Java
Java Program to Implement Sparse Array
Java Program to Implement Treap
The DAO with JPA and Spring
Java Program to Generate Random Numbers Using Multiply with Carry Method
Introduction to the Functional Web Framework in Spring 5
How to Use if/else Logic in Java 8 Streams
A Guide to @RepeatedTest in Junit 5
Lập trình đa luồng với CompletableFuture trong Java 8
Guide to System.gc()
Introduction to Using Thymeleaf in Spring
Java Program to Perform Cryptography Using Transposition Technique
Spring Security Authentication Provider
Hướng dẫn Java Design Pattern – Facade
Spring Boot Tutorial – Bootstrap a Simple Application