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.

  1. /**
  2.  ** Java Program to Implement Floyd Cycle Algorithm 
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.List;
  7. import java.util.ArrayList;
  8.  
  9. /** Class FloydCycle **/
  10. public class FloydCycle
  11. {
  12.     private List<Integer> func;
  13.     private int lam, mu; 
  14.     /** Constructor **/
  15.     public FloydCycle(List<Integer> list, int x0)
  16.     {
  17.         func = list;
  18.         /** print sequence **/
  19.         printSequence(x0);
  20.         /** find cycle **/
  21.         findCycle(x0);
  22.         /** display results **/
  23.         display();
  24.     }
  25.     /** function to find cycle **/
  26.     private void findCycle(int x0)
  27.     {
  28.         int tortoise = f(x0);    
  29.         int hare = f(f(x0));    
  30.         while (tortoise != hare)
  31.         {
  32.             tortoise = f(tortoise);
  33.             hare = f(f(hare));
  34.         }
  35.         int mu = 0;
  36.         tortoise = x0;
  37.         while (tortoise != hare)
  38.         {
  39.             tortoise = f(tortoise);
  40.             hare = f(hare);
  41.             mu += 1;
  42.         }
  43.         int lam = 1;
  44.         hare = f(tortoise);
  45.         while (tortoise != hare)
  46.         {
  47.             hare = f(hare);
  48.             lam += 1;
  49.         }
  50.         this.lam = lam;
  51.         this.mu = mu;
  52.     }
  53.     /** function to return value of function f(x) **/
  54.     private int f(int p)
  55.     {
  56.         return func.get(p);
  57.     }
  58.     /** function to print first n sequence **/
  59.     public void printSequence(int x0)
  60.     {
  61.         int n = func.size();
  62.         int tempx = x0;
  63.         System.out.print("\nFirst "+ n +" elements in sequence : \n"+ tempx);
  64.         for (int i = 0; i < n; i++)
  65.         {
  66.             tempx = f(tempx);
  67.             System.out.print(" "+ tempx);
  68.         }
  69.         System.out.println();        
  70.     }
  71.     /** function to display results **/
  72.     public void display()
  73.     {
  74.         System.out.println("\nLength of cycle : "+ lam);
  75.         System.out.println("Position : "+ (mu + 1));
  76.     }
  77.     /** Main function **/
  78.     public static void main(String[] args)
  79.     {
  80.         Scanner scan = new Scanner(System.in);
  81.         System.out.println("Floyd Cycle Algorithm Test\n");
  82.         System.out.println("Enter size of list");
  83.         int n = scan.nextInt();
  84.         List<Integer> list = new ArrayList<Integer>();
  85.         System.out.println("\nEnter f(x)");
  86.         for (int i = 0; i < n; i++)
  87.             list.add(scan.nextInt());
  88.         System.out.println("\nEnter x0");
  89.         int x0 = scan.nextInt();
  90.         FloydCycle fc = new FloydCycle(list, x0);
  91.     }
  92. }

advertisement
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.