Java Program to Implement Floyd Cycle Algorithm

This is a Java Program to Implement Floyd Cycle Algorithm. Cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. Floyd’s cycle-finding algorithm, also called the “tortoise and the hare” algorithm, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

Here is the source code of the Java Program to Implement Floyd Cycle Algorithm . The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to Implement Floyd Cycle Algorithm 
 **/
 
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
 
/** Class FloydCycle **/
public class FloydCycle
{
    private List<Integer> func;
    private int lam, mu; 
    /** Constructor **/
    public FloydCycle(List<Integer> list, int x0)
    {
        func = list;
        /** print sequence **/
        printSequence(x0);
        /** find cycle **/
        findCycle(x0);
        /** display results **/
        display();
    }
    /** function to find cycle **/
    private void findCycle(int x0)
    {
        int tortoise = f(x0);    
        int hare = f(f(x0));    
        while (tortoise != hare)
        {
            tortoise = f(tortoise);
            hare = f(f(hare));
        }
        int mu = 0;
        tortoise = x0;
        while (tortoise != hare)
        {
            tortoise = f(tortoise);
            hare = f(hare);
            mu += 1;
        }
        int lam = 1;
        hare = f(tortoise);
        while (tortoise != hare)
        {
            hare = f(hare);
            lam += 1;
        }
        this.lam = lam;
        this.mu = mu;
    }
    /** function to return value of function f(x) **/
    private int f(int p)
    {
        return func.get(p);
    }
    /** function to print first n sequence **/
    public void printSequence(int x0)
    {
        int n = func.size();
        int tempx = x0;
        System.out.print("\nFirst "+ n +" elements in sequence : \n"+ tempx);
        for (int i = 0; i < n; i++)
        {
            tempx = f(tempx);
            System.out.print(" "+ tempx);
        }
        System.out.println();        
    }
    /** function to display results **/
    public void display()
    {
        System.out.println("\nLength of cycle : "+ lam);
        System.out.println("Position : "+ (mu + 1));
    }
    /** Main function **/
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Floyd Cycle Algorithm Test\n");
        System.out.println("Enter size of list");
        int n = scan.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        System.out.println("\nEnter f(x)");
        for (int i = 0; i < n; i++)
            list.add(scan.nextInt());
        System.out.println("\nEnter x0");
        int x0 = scan.nextInt();
        FloydCycle fc = new FloydCycle(list, x0);
    }
}
Floyd Cycle Algorithm Test
 
Enter size of list
9
 
Enter f(x)
6 6 0 1 4 3 3 4 0
 
Enter x0
2
 
First 9 elements in sequence :
2 0 6 3 1 6 3 1 6 3
 
Length of cycle : 3
Position : 3

Related posts:

Giới thiệu Json Web Token (JWT)
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Registration – Password Strength and Rules
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Spring MVC Custom Validation
Java Copy Constructor
Java Program to Perform LU Decomposition of any Matrix
The Thread.join() Method in Java
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Constructor Dependency Injection in Spring
Hướng dẫn Java Design Pattern – Abstract Factory
Query Entities by Dates and Times with Spring Data JPA
Upload and Display Excel Files with Spring MVC
Map Interface trong java
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Check if a String is a Palindrome in Java
Send email with authentication
Lớp HashMap trong Java
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Implement Gauss Jordan Elimination
Jackson – JsonMappingException (No serializer found for class)
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Java Program to Implement Sorted Doubly Linked List
Tính kế thừa (Inheritance) trong java
Java Program to Compute Determinant of a Matrix
DynamoDB in a Spring Boot Application Using Spring Data
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
Java Program to Perform Stooge Sort
Handle EML file with JavaMail
Java Program to Check Cycle in a Graph using Graph traversal
Thao tác với tập tin và thư mục trong Java