Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
(25) [Topological sorting with cycle detection] Textbook Exercise 3 in Chapter 3. Assume the input graph is directed but may or may not have cycle in it, that is, may or may not be a directed acyclic graph. Consider the recursive topological sorting algorithm shown below.
TopologicalSort(G) {
If G has only one node v then return v.
Find a node v with no incoming edge and remove v from G.
Return v followed by the order returned by TopologicalSort(G).
}
Extend the recursive algorithm shown below so it can detect and output a cycle if the input graph G is not a directed acyclic graph. Clearly mark the extended part of the algorithm and state your reasoning behind the extension made. Hint: Lemma 3.19 in the textbook.
Additionally, explain how you can keep the running time O(m+n) with the extension.
(25) [Strongly connected graph] Prove or disprove the claim that a directed connected graph is strongly connected if every node in the graph has at least one incoming edge and at least one outgoing edge.
Last modified: September 12, 2019
