Printing(not detecting) cycle with topological sor

问题:

This is a question in a Data Structures and Algorithm Analysis 3rd edition which was also asked in one of our exams. Write down an algorithm to topologically sort a graph represented by an adjacency list, modified such that the algorithm prints out a cycle, if it is found. First, explain your idea in a few sentences. (Don’t use depth first search, we want just a modification of the basic topological sort.)

And the answer is: If no vertex has indegree 0, we can find a cycle by tracing backwards through vertices with positive indegree; since every vertex on the trace back has a positive indegree, we eventually reach a vertex twice, and the cycle has been found.

I didn't understand the part tracing back.What does it mean by "tracing back", and I wonder how would the pseudocode of this answer would be?. Appreciate any help.

回答1:

Kahns algorithm works by choosing a node with indegree 0, and removing all its outgoing edges (which may produce new nodes with indegree 0). If no more nodes of indegree 0 are found (and the graph is not empty now), it contains a cycle.

To print the cycle, start anywhere, and follow the incoming edges. Since there is a finite number of nodes, at some point you have to reach a node the second time. This is your cycle, to print it, just run it another time.

Say our graph is:

a --> b
b --> c, d
c --> b

inversion of this graph then is

a <-- 
b <-- a, c
c <-- b
d <-- b

Topological sort starts with a, removes it. b now is b <-- c

Now we start anywhere, say, d and search backwards.

d <-- b <-- c <-- b

Since we've seen b before, it must be part of the cycle. To print, we follow the links again and get b <-- c <-- b.

If there were any dead end - such as a - it would have been removed by the topological sort algorithm already prior to detecting the cycle.