# Are these algorithms for detecting cycles in directional graph correct?

I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not reachable from a given root. The useful debug information does not need to be exact (i.e. it is not a problem if the program prints few nodes not belonging to the cycle, as long as the nodes belonging to the cycle are among the output).

I created the following algorithm

function cycle_detect(node current_node, set<node> &parents)
if (current_node in parents)
print("cycle found")
for (parent in parents)
print(parent)
exit(1)
end if
for (child_node in current_node.children)
cycle_detect(child_node, parents)
end for
parents.remove(current_node)
end function


Here the set<node> & is a reference to a set that is initially empty. The algorithm is called as follows:

set<node> parents = empty_set();
cycle_detect(root_node, parents)


This algorithm should print the nodes belonging to the cycle, and the nodes from the parent node to the cycle.

My question is: is my algorithm correct? I assume it is not optimal (has less than optimal running time), but that's not what I'm looking for currently. I'm looking for an algorithm that is (a) simple to implement; (b) prints useful debug information.

If the algorithm is correct, what is its running time? My intuition is it's O(exp(N)) in the worst case. However, I don't believe the worst case running time would occur all that often. (I'm creating a tool the input to which cannot be constructed by malicious actors.)

Is there any simple way to improve the performance of this algorithm to let's say O(N^2)?

I'm thinking perhaps this algorithm should work:

function cycle_detect2(node current_node, set<node> &parents, set<node> &no_cycles)
if (current_node in no_cycles)
return
end if
if (current_node in parents)
print("cycle found")
for (parent in parents)
print(parent)
exit(1)
end if
for (child_node in current_node.children)
cycle_detect2(child_node, parents, no_cycles)
end for
parents.remove(current_node)
end function


The algorithm is called as follows:

set<node> parents = empty_set();
set<node> no_cycles = empty_set();
cycle_detect2(root_node, parents, no_cycles)


Is this second algorithm correct? Am I right in that it's O(N^2) if the set is a hash set? If it's a tree set, it's O(N^2 log(N)), right? Here N refers to the node count, not to the arc count.

• There are standard polynomial-time algorithms for cycle detection in graphs. Just use them, especially if you have any reason at all to suspect that your own algorithm is exponential! – David Richerby May 4 at 11:06
• Now that I searched for cycle detection algorithms for graphs, I found this which seems very similar to my second algorithm: geeksforgeeks.org/detect-cycle-in-a-graph – juhist May 4 at 11:11