as with dfswe can extend breadth-first search (bfsto work for directed graphs the algorithm still visits vertices level by level and partitions the set of edges into tree edges (or discovery edges)which together form directed breadth-first search tree rooted at the start vertexand nontree edges unlike the directed dfs methodhoweverthe directed bfs method only leaves two kinds of nontree edgesback edgeswhich connect vertex to one of its ancestorsand cross edgeswhich connect vertex to another vertex that is neither its ancestor nor its descendent there are no forward edgeswhich is fact we explore in an exercise ( - transitive closure in this sectionwe explore an alternative technique for computing the transitive closure of digraph let be digraph with vertices and edges we compute the transitive closure of in series of rounds we initialize we also as we then begin the arbitrarily number the vertices of computation of the roundsbeginning with round in generic round kwe construct digraph starting with and adding to the directed contains both the edges ( , and ( , in this edge ( if digraph waywe will enforce simple rule embodied in the proposition that follows proposition for = ,ndigraph only if digraph has directed path from to whose intermediate vertices (if anyare in the set{ , in particularclosure of has an edge ( if and is equal to the transitive proposition suggests simple algorithm for computing the transitive closure of that is based on the series of rounds we described above this algorithm is known as the floyd-warshall algorithmand its pseudo-code is given in code fragment from this pseudo-codewe can easily analyze the running time of the floyd-warshall algorithm assuming that the data structure representing supports methods areadjacent and insertdirectededge in ( time the main loop is executed times and the inner loop considers each of ( pairs of verticesperforming constant-time computation for each one thusthe total running time of the floyd-warshall algorithm is ( code fragment pseudo-code for the floydwarshall algorithm this algorithm computes the