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|

Question

Computers & Technology

Jazlene Jacobs

18 May, 19:50

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|

+3

Answers (1)

Know the Answer?

Makenzie · Answer 1

Check the explanation

Explanation:

We can utilize the above algorithm with a little in modification. If in each of the iteration, we discover a node with no inward edges, then we we're expected succeed in creating a topological ordering.

If in a number of iteration, it becomes apparent that each of the node has a minimum of one inward edge, then there must be a presence of cycle in the graph.

So our algorithm in finding the cycle is this: continually follow an edge into the node we're presently at (which is by choosing the first one on the adjacency list of inward edges to decrease the running time).

Since the entire node has an inward edge, we can do this continually or constantly until we revisit a node v for the first time.

The set of nodes that we will come across among these two successive visits is a cycle (which is traversed in the reverse direction).