graphs the connectivity table you can easily modify the dfs java program (listing to start the search on each vertex in turn for the graph of figure the output will look something like thisac bace dec ec this is the connectivity table for the directed graph the first letter is the starting vertex and subsequent letters show the vertices that can be reached (either directly or via other verticesfrom the starting vertex warshall' algorithm in some applications it' important to find out quickly whether one vertex is reachable from another vertex perhaps you want to fly from athens to murmansk on hubris airlines and you don' care how many intermediate stops you need to make is this trip possibleyou could examine the connectivity tablebut then you would need to look through all the entries on given rowwhich would take (ntime (where is the average number of vertices reachable from given vertexbut you're in hurryis there faster wayit' possible to construct table that will tell you instantly (that isin ( timewhether one vertex is reachable from another such table can be obtained by systematically modifying graph' adjacency matrix the graph represented by this revised adjacency matrix is called the transitive closure of the original graph remember that in an ordinary adjacency matrix the row number indicates where an edge starts and the column number indicates where it ends (this is similar to the arrangement in the connectivity table at the intersection of row and column means there' an edge from vertex to vertex you can get from one vertex to the other in one step (of coursein directed graph it does not follow that you can go the other wayfrom to table shows the adjacency matrix for the graph of figure table adjacency matrix