CODEWITHSUNDEEP
algorithmgraph-algorithm
woryzower
woryzower

Reputation: 976

Printing(not detecting) cycle with topological sort

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.

Upvotes: 4

Views: 2667

Answers (2)

Nikhil badam
Nikhil badam

Reputation: 1

After completing the process of topological sorting( i.e., selecting a vertex with in-degree 0, removing it, decreasing its children indegree by 1, then repeat the process), if suppose there are still some vertices left to be explored and we can't find any vertex with in-degree 0, this means that we have a cycle in the subgraph formed by leftover unexplored vertices since in a DAG there must be at least one vertex with in-degree 0. We then pick-up a vertex from these left-over vertices, trace around the graph until you reach the starting vertex, this is the cycle.

Upvotes: 0

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77474

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.

Upvotes: 4

Related Questions