performing dfs of directed graph from each of its verticesbut this depends upon the representation of the graph if graph is represented using an adjacency matrixthen running the dfs method once on directed graph takes ( time (we explore the reason for this in exercise - thusrunning dfs times takes ( timewhich is no better than single execution of the floyd-warshall algorithmbut the floyd-warshall algorithm would be much simpler to implement neverthelessif the graph is represented using an adjacency list structurethen running the dfs algorithm times would take ( ( + )time to compute the transitive closure even soif the graph is densethat isif it has &( edgesthen this approach still runs in ( time and is more complicated than single instance of the floyd-warshall algorithm the only case where repeatedly calling the dfs method is better is when the graph is not dense and is represented using an adjacency list structure directed acyclic graphs directed graphs without directed cycles are encountered in many applications such digraph is often referred to as directed acyclic graphor dagfor short applications of such graphs include the followinginheritance between classes of java program prerequisites between courses of degree program scheduling constraints between the tasks of project example in order to manage large projectit is convenient to break it up into collection of smaller tasks the taskshoweverare rarely independentbecause scheduling constraints exist between them (for examplein house building projectthe task of ordering nails obviously precedes the task of nailing shingles to the roof deck clearlyscheduling constraints cannot have circularitiesbecause they would make the project impossible (for examplein order to get job you need to have work experiencebut in order to get work experience you need to have job the scheduling constraints impose restrictions on the order in which the tasks can be executed namelyif constraint says that task must be completed before task is startedthen must precede in the order of execution of the tasks thusif we model feasible set of tasks as vertices of directed graphand we place directed edge from tow whenever the task for must be executed before the task for wthen we define directed acyclic graph the example above motivates the following definition let be digraph with vertices topological ordering of is an ordering , of the vertices of such that for every edge (vivjof that isa topological ordering is an