This Java program is to find the transitive closure of a graph.Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph.
Here is the source code of the Java program to find the transitive closure of graph. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Scanner; public class TransitiveClosure { private int transitiveMatrix[][]; private int numberofvertices; public static final int INFINITY = 999; public TransitiveClosure(int numberofvertices) { transitiveMatrix= new int[numberofvertices + 1][numberofvertices + 1]; this.numberofvertices = numberofvertices; } public void transitiveClosure(int adjacencymatrix[][]) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { transitiveMatrix[destination] = adjacencymatrix[destination]; } } for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { if (transitiveMatrix[intermediate] + transitiveMatrix[intermediate][destination] < transitiveMatrix[destination]) transitiveMatrix[destination] = transitiveMatrix[intermediate] + transitiveMatrix[intermediate][destination]; } } } for (int source = 1; source <= numberofvertices; source++) System.out.print("\t" + source); System.out.println(); for (int source = 1; source <= numberofvertices; source++) { System.out.print(source + "\t"); for (int destination = 1; destination <= numberofvertices; destination++) { System.out.print(transitiveMatrix[destination] + "\t"); } System.out.println(); } } public static void main(String... arg) { int adjacency_matrix[][]; int numberofvertices; Scanner scan = new Scanner(System.in); System.out.println("Enter the number of vertices"); numberofvertices = scan.nextInt(); adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1]; System.out.println("Enter the Weighted Matrix for the graph"); for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { adjacency_matrix[destination] = scan.nextInt(); if (source == destination) { adjacency_matrix[destination] = 0; continue; } if (adjacency_matrix[destination] == 0) { adjacency_matrix[destination] = INFINITY; } } } System.out.println("The Transitive Closure of the Graph"); TransitiveClosure transitiveClosure = new TransitiveClosure(numberofvertices); transitiveClosure.transitiveClosure(adjacency_matrix); scan.close(); } }
$javac TransitiveClosure.java $java TransitiveClosure Enter the number of vertices 4 Enter the Weighted Matrix for the graph 0 0 3 0 2 0 0 0 0 7 0 1 6 0 0 0 The Transitive Closure of the Graph 1 2 3 4 1 0 10 3 4 2 2 0 5 6 3 7 7 0 1 4 6 16 9 0
Related posts:
Phương thức tham chiếu trong Java 8 – Method References
Java Program to Perform LU Decomposition of any Matrix
HashSet trong java
Wiring in Spring: @Autowired, @Resource and @Inject
Introduction to the Java NIO Selector
Sử dụng CountDownLatch trong Java
Jackson JSON Views
Java Program to Implement Hash Trie
Spring Boot - Google Cloud Platform
Java Program to implement Sparse Vector
Introduction to Spring Boot CLI
Create a Custom Exception in Java
Request a Delivery / Read Receipt in Javamail
Java Program to Implement Range Tree
Java – Reader to String
Java Program to find the peak element of an array using Binary Search approach
Compare Two JSON Objects with Jackson
The Thread.join() Method in Java
Java Program to Construct K-D Tree for 2 Dimensional Data
Java Program to Find Minimum Element in an Array using Linear Search
Send email with SMTPS (eg. Google GMail)
Java Program to Implement String Matching Using Vectors
Guide to java.util.concurrent.Locks
Java Program to Show the Duality Transformation of Line and Point
DistinctBy in the Java Stream API
Java Program to Represent Graph Using Incidence Matrix
Spring Boot - Exception Handling
Java Program to Solve Knapsack Problem Using Dynamic Programming
Java Program to Perform Addition Operation Using Bitwise Operators
Extra Login Fields with Spring Security
Spring Boot - Securing Web Applications
Java Program to Implement TreeMap API