Question

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). }

(a) 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.

Answer 1

(a) We notice that at any instant , if there does not exist any node v such that there is no incoming edge to v then we have a cycle in the graph. Thus, a topological sorting of the graph doesn't exist in such a case.

We maintain an adjacency list for the Directed graph, InAdj

In  InAdj , for each vertex u,we maintain all vertices v such that there is an incoming edge from v to u

We maintain a global list topoList which contains the nodes sorted in topological order .

We write the pseudo Code for recursive Topo sort below

Main(G) : // G is the input directed graph

1. Initialize InAdj

2. topoList = { }

3. val = RecurTopoSort // if val = 0 then there is cycle in the graph else graph's a DAG

4. if (val == 0)

5. print "There is cycle in the directed graph"

6. else

7. for each vertex v   topoList // print vertex v in order which they appear in topoList

8. print v  

RecurTopoSort:

1. isNodeExists = false

2. if (InAdj is empty) // if Adjacency list is empty

3. return 1 // 1 is returned when no cycle is encountered in graph G     

4. for each vertex u  InAdj

5.  if ( InAdj[u] is empty) // there exists a node u with no incoming edge

6.   isNodeExists = true

7.   Remove the node u from the all the entries in InAdj

8.   break

9. if (isNodeExists == true)

10.   topoList.push(u)

11.   return RecurTopoSort

12. else

13.   return 0