Topological sorting

Question

Consider the following topological sorting algorithm in my tutorial:

Input: A digraph G with n vertices Output: A topological ordering v1,v2...vn of G, or the non-existence thereof. S is an empty stack for each vertex u in G do incount(u) = indeg(u) if incount(u) == 0 then S.push(u) i = 1 while S is non-empty do u = S.pop() set u as the i-th vertex vi i ++ for each vertex w forming the directed edge (u,w) do incount(w) -- if incount(w) == 0 then S.push(w) if S is empty then return "G has a dicycle" 

I tried to implement the algorithm to the word, but found that he always complained about the bike, regardless of whether the graph was acyclic or not. Then I found that the last two lines did not fit correctly. The while loop just before it ends when S is empty. Thus, each time, he is sure that the if condition will remain true.

How can I fix this algorithm to correctly check the bike?

Edit:

For the time being, I will just get around the S problem by checking the value of I at the end:

 if i != n + 1 return "G has a dicycle" 

Answer 1

Your fix is ​​correct. If you did not click all the nodes in the graph on S , the graph contains at least one strongly connected component. In other words, you have a loop.