Search code examples
loopsdetectioncycle

Loop detection in connected graph

Most example I found only treat single linked lists. I need a solution for a multiple linked list.

Image is easier (valid):

enter image description here

Invalid:

enter image description here

Which algorithm would be able to return the begining of the loop (B) and not collide with E? A good starting point would be also to know if there is a loop at all. Stuff like this or edge counting doesn't work (because not single linked...).

Thanks.

Solution

  • Just check if a route from 'end of connection node (B)' to 'start of connection node (C)' exists, if yes, a new loop would be created. Doesn't quite answer it, but good enough...