How do I find a cycle in a directed graph using topological sort?

Question

I have implemented this pseudocode in my program to check if a directed graph is acyclic:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

This works great, but I also need to output the actual cycle if the graph isn't acyclic. Is it possible to do this "inside" this code, or do I need to change my algorithm completely? I have tried to search for a solution, and I found this answer (Printing(not detecting) cycle with topological sort) but I can't understand how to actually do this. Does anyone have some pseudocode that could help me?

Have you read about color maps in graph algorithms? Detecting a cycle is trivial once you have a proper DFS algorithm using a color map. If you ever follow an edge and encounter a gray vertex, you have found a cycle. Since you want to print the vertices comprised by the cycle, you can unwind your current stack of vertices being explored, all the way back until you find that same offending gray vertex again in your stack. — seh
I haven't read about this, but it seems like a better plan. Still, I would like to use the solution I have already implemented as my whole program (a quite big one) depends on the topological sorting. If I don't get it to work I'll definetly look at your suggestion :) — user16655
I wasn't clear enough: In order to sort topologically, you run a depth-first walk ("DFW", not DFS, as there's no searching involved), and only emit the black vertices in order if you don't find a cycle. Hence, the DFW both ensures your graph is acyclic and sorts topologically at the same time. DFW and topological sort are not mutually exclusive; you implement topological sort in terms of DFW. — seh

Gil Moshayof Gil Moshayof · Accepted Answer · 2014-10-27T15:28:15

First of all, what you're trying to do is a bit problematic, since there may be more than one cycle. Theoretically, every node in the graph could have a self pointing edge, then there'll be n cycles.

However, an easy approach would be to grab any edge in the graph, then iterate over it until you reach back to the same edge, and output this as a cycle. Edges which result in dead-ends should be removed, and any cycle found should remove all the cycle edges from the graph as well. Keep doing this until the graph has no more edges and this should output all the cycles in the graph, albeit in no particular order or optimisation, and may miss some cycles if performed in a certain order.

How do I find a cycle in a directed graph using topological sort?

1 Answers