อัลกอริธึมการตรวจจับวัฏจักรฟลอยด์เพื่อตรวจจับวัฏจักรในโครงสร้างข้อมูลเชิงเส้น

Floyd Cycle เป็นหนึ่งในอัลกอริธึมการตรวจจับวัฏจักรเพื่อตรวจจับวัฏจักรในรายการที่เชื่อมโยงโดยลำพัง

ในอัลกอริธึม Floyd Cycle เรามีตัวชี้สองตัวที่เริ่มแรกชี้ไปที่ส่วนหัว ในเรื่อง Hare and Tortoise Hare เคลื่อนที่เร็วเป็นสองเท่าของ Tortoise และเมื่อใดก็ตามที่กระต่ายมาถึงจุดสิ้นสุดของเส้นทาง เต่าจะไปถึงกลางเส้นทาง

อัลกอริทึม

• เริ่มต้น Hare และ Tortoise ที่ส่วนหัวของ List

• ในขั้นต้น กระต่ายจะเคลื่อนไหวเร็วกว่าเต่าสองเท่า

• ย้ายกระต่ายและเต่าทั้งคู่และดูว่ากระต่ายถึงจุดสิ้นสุดของรายการที่เชื่อมโยงหรือไม่ ให้กลับเนื่องจากไม่มีการวนซ้ำในรายการ

• มิฉะนั้น ทั้งกระต่ายและเต่าจะก้าวไปข้างหน้า

• หากกระต่ายและเต่าอยู่ที่โหนดเดียวกัน ให้กลับมาเนื่องจากเราพบวงจรรายการแล้ว

• อย่างอื่น เริ่มด้วยขั้นตอนที่ 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'