플로이드의 사이클 찾기 알고리즘 - 두 개의 포인터가 필요합니까?

Question

오늘 플로이드의주기 찾기 알고리즘을 사용하고 있으며 의심의 여지가있었습니다. 왜 그는 두 개의 포인터가 필요하고 다른 속도로 이동시킬 수 있습니까?

그는 두 개의 포인터를 만들어서 정적으로 유지하고 그 포인터를 다른 포인터와 비교할 수 있습니다. 나는 그것이 심지어 사이클을 찾는 결과를 가져올 것이라는 것을 의미합니까?

Answer 1

이동해야하는 이유는주기가 반드시 노드 목록 전체를 반복 할 필요가 없기 때문입니다.

예를 들어, 우리는 하나의 포인터가, 우리가주기를 감지하지 않겠다고에서 지적 유지하면 우리가 4 개 노드 A-> B-> C-> D-> B

가 있다고 가정 해 보자.

Answer 2

이유는 순환을 벗어나는 모든 분기에서 포인터를 가져 오기 위해 뒤쪽에있는 포인터가 증가해야하기 때문입니다.

예 :

두 포인터가 모두 E에서 시작한다고 가정하면, 한 포인터를 변경하지 않으면 다른 포인터는 변경되지 않습니다. E => D => B => C => A => B => C => ... 절대 도착하지 마십시오.

다른 사람들은 알고리즘의 복잡성이 같지 않다고 말하면서 모든 단일 정점 (느린)부터 시작해야한다는 것을 의미합니다. 빠른/느린 포인터 메서드를 사용하면 그래프의 각 "구성 요소"에서 시작하기 만하면됩니다. 구성 요소는 서로 연결된 모든 꼭짓점입니다. 별도의 구성 요소는 꼭지점이 모서리로 연결되지 않는다는 의미입니다.

느린 포인터를 늘리면 A => B => C 사이클이됩니다.

포인터 변경의 유효 차이가 단지 1이기 때문에 결코 놓치지 않을 것입니다. 즉. 빠른 포인터가 느린 포인터를 따라 잡으면 두 포인터 사이의 거리가 반복마다 1 씩만 변경됩니다. 따라서 결국 거리는 0에 도달하게됩니다.