Detecting a cycle in a graph

[Christian Gollwitzer]

Am 14.01.18 um 09:30 schrieb Frank Millman:
> I need to detect when a 'cycle' occurs - when a path loops back on 
> itself and revisits a node previously visited. I have figured out a way 
> to do this, but I have a problem.

I don't know if that helps, but there is a classic graph theory 
algorithm called "Floyd's cycle detector". The idea is to have a pointer 
move along the graph and a second one which runs at double the speed. If 
they meet, you found a cycle. It is not straight-forward to come up with 
this algorithm, which even runs in constant storage. ISTR that there are 
some variants which can give you the split point of the cycle, too.

	Christian