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 * * *

**Sanfoundry Global Education & Learning Series – 1000 Java Programs.**

advertisement

advertisement

If you wish to look at all Java Programming examples, go to Java Programs.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Programming Books
- Practice Information Technology MCQs
- Apply for Computer Science Internship
- Check Java Books
- Practice BCA MCQs