Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

선형 데이터 구조에서 주기를 감지하는 Floyd 주기 감지 알고리즘

<시간/>

Floyd 주기는 주어진 단일 연결 목록에서 주기를 감지하는 주기 감지 알고리즘 중 하나입니다.

Floyd Cycle 알고리즘에는 처음에 머리를 가리키는 두 개의 포인터가 있습니다. 토끼와 거북이 이야기에서 토끼는 거북이보다 2배 빠르게 움직이며 토끼가 길의 끝에 도달할 때마다 거북이는 길의 중간에 도달합니다.

알고리즘

  • List의 헤드 노드에서 Hare와 Tortoise를 초기화합니다.

  • 처음에는 토끼가 거북이보다 두 배 빠르게 움직입니다.

  • 토끼와 거북이 둘 다 움직여서 토끼가 연결 목록의 끝에 도달했는지 확인하고 목록에 루프가 없으므로 반환합니다.

  • 그렇지 않으면 토끼와 거북이가 모두 앞으로 나아갑니다.

  • Hare와 Tortoise가 같은 노드에 있으면 목록 주기를 찾았으므로 반환합니다.

  • 그렇지 않으면 2단계부터 시작하세요.

위 알고리즘에 대한 의사 코드

tortoise := headNode
hare := headNode
foreach:
   if hare == end
      return 'There is No Loop Found.'
   hare := hare.next
   if hare == end
      return 'No Loop Found'
   hare = hare.next
   tortoise = tortoise.next
   if hare == tortoise
      return 'Cycle Detected'