Floyd Cycle là một trong những thuật toán phát hiện chu trình để phát hiện chu trình trong một danh sách được liên kết riêng lẻ nhất định.
Trong thuật toán Floyd Cycle, chúng ta có hai con trỏ ban đầu trỏ vào đầu. Trong câu chuyện của Hare và Tortoise, Hare di chuyển nhanh gấp đôi so với Rùa và bất cứ khi nào thỏ đi đến cuối con đường, con rùa sẽ đến giữa con đường.
Thuật toán
-
Khởi tạo Hare và Tortoise ở nút đầu của Danh sách.
-
Ban đầu, thỏ rừng di chuyển nhanh gấp đôi rùa.
-
Di chuyển cả thỏ rừng và rùa và tìm xem thỏ rừng có đến cuối Danh sách được liên kết hay không, hãy quay lại vì không có vòng lặp nào trong danh sách.
-
Nếu không, cả Hare và Tortoise sẽ tiếp tục.
-
Nếu Hare và Tortoise ở cùng một Node, thì hãy quay lại vì chúng ta đã tìm thấy chu kỳ danh sách.
-
Nếu không, hãy bắt đầu với bước 2.
Mã giả cho thuật toán trên
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'