# Warshall’s algorithm

Lab 6

Implement Warshall’s algorithm to find the transitive closure for a graph.

class WarshallApp

{

public static void main(String[] args) throws IOException

{

Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0

theGraph.addVertex('B'); // 1

theGraph.addVertex('C'); // 2

theGraph.addVertex('D'); // 3

theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 2); // AC

theGraph.addEdge(1, 0); // BA

theGraph.addEdge(1, 4); // BE

theGraph.addEdge(3, 4); // DE

theGraph.addEdge(4, 2); // EC

System.out.println("Original adjacency matrix");

theGraph.adjMatDisplay(); // display adj matrix

theGraph.warshall(); // do the algorithm

System.out.println();

}

}

If you are using the above codes in your solution, the output will looks like:

Original adjacency matrix

A B C D E

====================

A 0 0 1 0 0

B 1 0 0 0 1

C 0 0 0 0 0

D 0 0 0 0 1

E 0 0 1 0 0

Transitive closure

A B C D E

====================

A 0 0 1 0 0

B 1 0 1 0 1

C 0 0 0 0 0

D 0 0 1 0 1

E 0 0 1 0 0

Implement Warshall’s algorithm to find the transitive closure for a graph.

class WarshallApp

{

public static void main(String[] args) throws IOException

{

Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0

theGraph.addVertex('B'); // 1

theGraph.addVertex('C'); // 2

theGraph.addVertex('D'); // 3

theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 2); // AC

theGraph.addEdge(1, 0); // BA

theGraph.addEdge(1, 4); // BE

theGraph.addEdge(3, 4); // DE

theGraph.addEdge(4, 2); // EC

System.out.println("Original adjacency matrix");

theGraph.adjMatDisplay(); // display adj matrix

theGraph.warshall(); // do the algorithm

System.out.println();

}

}

If you are using the above codes in your solution, the output will looks like:

Original adjacency matrix

A B C D E

====================

A 0 0 1 0 0

B 1 0 0 0 1

C 0 0 0 0 0

D 0 0 0 0 1

E 0 0 1 0 0

Transitive closure

A B C D E

====================

A 0 0 1 0 0

B 1 0 1 0 1

C 0 0 0 0 0

D 0 0 1 0 1

E 0 0 1 0 0

You'll get 1 file (5.0KB)