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:
Spring Boot With H2 Database
Spring Boot - Quick Start
Java Program to Find Number of Articulation points in a Graph
Java Timer
Java Program to Implement Hash Tables with Double Hashing
File Upload with Spring MVC
Java – Convert File to InputStream
Java Program to Solve Knapsack Problem Using Dynamic Programming
Practical Java Examples of the Big O Notation
Spring Cloud Connectors and Heroku
Spring MVC Custom Validation
Hướng dẫn Java Design Pattern – Flyweight
Java Program to implement Priority Queue
Spring Data MongoDB Transactions
Simplify the DAO with Spring and Java Generics
Java Program to Check whether Directed Graph is Connected using BFS
Custom Error Pages with Spring MVC
Java Program to Perform Finite State Automaton based Search
Spring @RequestMapping New Shortcut Annotations
Serialize Only Fields that meet a Custom Criteria with Jackson
Get and Post Lists of Objects with RestTemplate
Java Program to Implement PriorityQueue API
Câu lệnh điều khiển vòng lặp trong Java (break, continue)
Entity To DTO Conversion for a Spring REST API
Java Program to Implement Find all Forward Edges in a Graph
Lớp Arrarys trong Java (Arrays Utility Class)
Từ khóa static và final trong java
Java Program to Solve a Matching Problem for a Given Specific Case
JPA/Hibernate Persistence Context
How to Remove the Last Character of a String?
Guide to the Java Queue Interface
Java Multi-line String