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
Powered by