Detecting a cycle in a graph
Christian Gollwitzer
auriocus at gmx.de
Sun Jan 14 16:04:45 EST 2018
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
More information about the Python-list
mailing list