CODEWITHSUNDEEP
algorithmfloyd-cycle-finding
Viswanath Kuchibhotla
Viswanath Kuchibhotla

Reputation: 171

Floyd's cycle finding algorithm - Need for two pointers?

I was going through Floyd's cycle finding algorithm today and had a doubt. Why would he need two pointers and move them at different speeds?

He can instead create two pointers keep one static and compare the pointer of it with another pointer, which he increments? I mean even that will result in finding cycles right?

Upvotes: 4

Views: 1182

Answers (2)

ronalchn
ronalchn

Reputation: 12335

The reason is that the pointer that is behind (increased more slowly) needs to be increased to get it out of any branches coming off the cycle.

Eg. Edges A => B, B => C, C => A, D => B, E => D.

Suppose both pointers start at E. Then if you don't change one pointer, the other will go E => D => B => C => A => B => C => ..., and never get to E.

When others say you won't get the same algorithmic complexity, they mean you will have to try start from every single vertex (which is slower). With the fast/slow pointer method, you only have to try starting from each "component" of the graph ONCE. A component is all the vertices connected to each other. Separate components means that the vertices are not connected by edges.

By increasing the slow pointer, it will also get into the A => B => C cycle.

And it will never miss, because the effective difference in the change of pointers is only 1. ie. If the fast pointer is catching up to the slow pointer, the distance between them only changes by 1 each iteration. So eventually the distance will reach 0.

Upvotes: 4

brianestey
brianestey

Reputation: 8302

The reason they need to move is that the cycle doesn't necessarily have to loop the entire list of nodes.

For example, let's say we have 4 nodes A->B->C->D->B

If we kept one pointer pointed at A, we'd never detect the cycle.

Upvotes: 10

Related Questions