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:
OAuth2.0 and Dynamic Client Registration
Java Program to Implement the One Time Pad Algorithm
Java Program to Implement Suffix Array
Unsatisfied Dependency in Spring
Consuming RESTful Web Services
A Guide to ConcurrentMap
Java Program to Implement Shunting Yard Algorithm
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Spring Security Authentication Provider
Java – File to Reader
Introduction to Netflix Archaius with Spring Cloud
A Guide to the Java ExecutorService
Java – Generate Random String
Java Program to Implement Fermat Primality Test Algorithm
How to Store Duplicate Keys in a Map in Java?
Java Program to Implement Sorted List
Spring Boot: Customize Whitelabel Error Page
Introduction to Liquibase Rollback
How to Manually Authenticate User with Spring Security
A Guide to Spring Boot Admin
Java toString() Method
StringBuilder vs StringBuffer in Java
Java Program to Solve Knapsack Problem Using Dynamic Programming
Runnable vs. Callable in Java
Daemon Threads in Java
Java Program to Perform Left Rotation on a Binary Search Tree
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Java Program to Perform Uniform Binary Search
Giới thiệu JDBC Connection Pool
Guide to Dynamic Tests in Junit 5
Guide to Escaping Characters in Java RegExps
Java – Write an InputStream to a File