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:
Transactions with Spring and JPA
Database Migrations with Flyway
Java Program to Check for balanced parenthesis by using Stacks
Jackson Unmarshalling JSON with Unknown Properties
Java Program to Check if a Given Binary Tree is an AVL Tree or Not
Guava Collections Cookbook
Lập trình hướng đối tượng (OOPs) trong java
Spring Boot - Application Properties
Limiting Query Results with JPA and Spring Data JPA
Java 8 Predicate Chain
Java Program to Implement Unrolled Linked List
Java Program to Solve the 0-1 Knapsack Problem
Java Program to Perform Searching Based on Locality of Reference
Java Program to Describe the Representation of Graph using Adjacency Matrix
How to Kill a Java Thread
Wrapper Classes in Java
Java Program to Implement Binary Heap
Lớp TreeMap trong Java
Java Program to Implement CopyOnWriteArraySet API
Giới thiệu luồng vào ra (I/O) trong Java
Integer Constant Pool trong Java
Spring Data – CrudRepository save() Method
Java – Write to File
Giới thiệu Google Guice – Injection, Scope
Java Program to Implement Self organizing List
Tránh lỗi NullPointerException trong Java như thế nào?
CyclicBarrier in Java
Introduction to the Java NIO Selector
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
A Guide to Java HashMap
Spring Boot - Enabling Swagger2
Using JWT with Spring Security OAuth (legacy stack)