Question

Suppose we are given an arbitrary digraph G = (V, E) that may or may not be a DAG. Modify the topological ordering algorithm so that given an input G, it outputs one of the two things:

a. A topological ordering thus establishing that G is a DAG.

b. A cycle in G thus establishing that it is not a DAG.

The runtime of your algorithm should be O(m+n) where m = |E| and n = |V|

Answer 1

Answer:-

Given an arbitrary digraph G = (V,E)

a) A topological ordering thus it establishing that G :-

The algorithm that we know is a Topological - Sort (G)

• First select v ∈ G.V with no incoming edges
• Output v
• G.V = G.V-v
• Topological- Sort (G)

Modified algorithm:-

For every Iteration, we find a node with no incoming edges and then we will succeed in producing a topological ordering.

If in some iteration, it finds that every node has at least one incoming edge then the graph must contain a cycle.

b. A cycle in G thus establishing that it is not a DAG:-

If every node has at least one incoming edge then the graph must contain a cycle.

Now, follow the steps

Step 1:- Follow an edge into the node and do this repeatedly i.e., [lEl].

Step 2:- Since every node has an incoming edge, and do this repeatedly until we revisit a node 'v' for the first time i.e., [lVl].

Step 3:-Now, the set of nodes encountered between these 2 successive Visits(i.e., step 1 and step 2) is a cycle. Then,

• First visit , it will take O(IEl) to loop through every edge.
• Second visit, it will take O(lVl) to loop through every node.

Hence, The algorithm runs in O(lEl + IVl) = O(m+n). [ m = |E| and n = |V|]