Data StructuresMenengahFase D–FE1E5

FLOYD CYCLE

Algoritma Floyd (tortoise and hare) mendeteksi siklus pada linked list menggunakan dua pointer: slow bergerak satu langkah dan fast bergerak dua langkah setiap iterasi. Jika kedua pointer bertemu, berarti terdapat loop; jika fast mencapai akhir list, tidak ada siklus. Visualisasi menampilkan linked list berbentuk lingkaran dengan kedua pointer yang saling mengejar hingga bertemu di titik siklus.

Example use case

Mendeteksi loop tak terhingga pada struktur data terhubung atau siklus dalam graf dependensi.

Syllabus

Dua pointer berlari beda kecepatan pada linked list; bila yang cepat menyusul yang lambat, berarti ada siklus.

Objectives

·Memahami teknik dua pointer slow dan fast
·Menjelaskan mengapa pertemuan pointer menandakan adanya loop
·Menerapkan deteksi siklus pada struktur data terhubung

How It Works

·Tempatkan pointer slow dan fast di awal list
·Gerakkan slow satu langkah tiap iterasi
·Gerakkan fast dua langkah tiap iterasi
·Bila keduanya bertemu di titik sama, ada siklus
·Bila fast mencapai ujung list, tidak ada siklus

Prerequisites

·Linked list
·Konsep pointer

Real-World Uses

·Mendeteksi loop tak berujung di rantai data yang saling menunjuk
·Menemukan siklus di graf dependensi agar program tidak macet

Complexity O(n)