CODEWITHSUNDEEP
cycledirected-acyclic-graphstopological-sort
user16655
user16655

Reputation: 1941

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

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?

Upvotes: 3

Views: 8058

Answers (1)

Gil Moshayof
Gil Moshayof

Reputation: 16771

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.

Upvotes: 1

Related Questions