Run the DFS-based topological ordering algorithm on the following graph. Start the traversal at vertex A and whenever you have a choice of vertices to explore, always pick the one that is alphabetical first.

Indicate the pre and post numbers of the nodes.

What are the sources and sinks of the graph?

What topological ordering is found by the algorithm?

How many topological orderings does this graph have?

Can one use the order in which vertices are pushed onto the DFS stack (instead of the order they are popped off it) to solve the topological sorting problem?

According Theorem 3.1 (Parenthesis Theorem), we know that during the exploration process for a graph, for each node u, we can note down the times of first discovery (pre (u)) and finishing (post(u)) of the node. The pre and post number of each node can be associated our clock for push onto a stack or pop off from the stack.

Apply the source-removal algorithm to the diagraphs of Problem 3.

What is the time efficiency of the DFS-based algorithm for topological sorting?

How can one modify the DFS-based algorithm to avoid reversing the vertex ordering

generated by DFS?