transitive closure we have seen that graph traversals can be used to answer basic questions of reachability in directed graph in particularif we are interested in knowing whether there is path from vertex to vertex in graphwe can perform dfs or bfs traversal starting at and observe whether is discovered if representing graph with an adjacency list or adjacency mapwe can answer the question of reachability for and in ( mtime (see propositions and in certain applicationswe may wish to answer many reachability queries more efficientlyin which case it may be worthwhile to precompute more convenient representation of graph for examplethe first step for service that computes driving directions from an origin to destination might be to assess whether the destination is reachable similarlyin an electricity networkwe may wish to be able to quickly determine whether current flows from one particular vertex to another motivated by such applicationswe introduce the following definition the is itself directed graph such that the transitive closure of directed graph and has an edge (uv)whenare the same as the vertices of gvertices of ever has directed path from to (including the case where (uvis an edge of the original gif graph is represented as an adjacency list or adjacency mapwe can compute its transitive closure in ( ( )time by making use of graph traversalsone from each starting vertex for examplea dfs starting at vertex can be used to determine all vertices reachable from uand thus collection of edges originating with in the transitive closure in the remainder of this sectionwe explore an alternative technique for computing the transitive closure of directed graph that is particularly well suited for when directed graph is represented by data structure that supports ( )-time lookup for the get edge( ,vmethod (for examplethe adjacency-matrix structurelet be directed graph with vertices and edges we compute the transitive closure we also arbitrarily number the in series of rounds we initialize of vertices of as vn we then begin the computation of the roundsbegink starting ning with round in generic round kwe construct directed graph - with gk gk- and adding to gk the directed edge (vi if directed graph contains both the edges (vi vk and (vk in this waywe will enforce simple rule embodied in the proposition that follows has an edge (vi if and proposition for ndirected graph only if directed graph has directed path from vi to whose intermediate is equal to the vertices (if anyare in the set { vk in particularg transitive closure of