Adjacency Linked List Cycle Detection - Java

Question

I have some problem checking if my adjacency list has a cycle or not. I want to make a function that checks if my adjacency list has existing at least one cycle.

Based on my program. First, I have to input the Root Node, followed by a number of nodes, the nodes in the graph, number of edges, and the adjacency list representing the edges. Each entry in the adjacency list contains a pair of nodes.

Sample input:

Root node: "A"
Number of nodes: 3
Vertices/Nodes:
A
B
C
Number of edges: 3
A
B
B
C
C
A
A --> B
B --> C
C --> A

The sample input above has a cycle: [ A --> B --> C --> A ] I want to output whether it has a cycle or not.

This is my program so far:

import java.util.Scanner;
class Neighbor {
public int vertexNum;
public Neighbor next;
public Neighbor(int vnum, Neighbor nbr) {
 this.vertexNum = vnum;
 next = nbr;
 }
}
class Vertex {
String name;
Neighbor adjList;
Vertex(String name, Neighbor neighbors) {
 this.name = name;
 this.adjList = neighbors;
 }
}
public class DirectedCycle {
Vertex[] adjLists;
public DirectedCycle() {
 Scanner sc = new Scanner(System.in);
 //Root Node
 System.out.print("Root node: ");
 String rn = sc.nextLine();
 //Number of nodes
 System.out.print("Number of vertices/nodes: ");
 int nodes = sc.nextInt();
 adjLists = new Vertex[nodes];
 //List of nodes
 System.out.println("Vertices:");
 for (int v=0; v < adjLists.length; v++) {
 String letter = sc.next();
 adjLists[v] = new Vertex(letter, null);
 }
 //Number of edges
 System.out.print("Number of edges: ");
 int edges = sc.nextInt();
 System.out.println("<v1> <v2>");
 for(int i=0; i<edges; i++) {
 int v1 = indexForName(sc.next());
 int v2 = indexForName(sc.next());
 adjLists[v1].adjList = new Neighbor(v2, adjLists[v1].adjList);
 }
}
int indexForName(String name) {
 for (int v=0; v < adjLists.length; v++) {
 if (adjLists[v].name.equals(name)) {
 return v;
 }
 }
 return -1;
} 
public void print() {
 System.out.println();
 for (int v=0; v < adjLists.length; v++) {
 System.out.print(adjLists[v].name);
 for (Neighbor nbr=adjLists[v].adjList; nbr != null; nbr=nbr.next) {
 String name = adjLists[nbr.vertexNum].name;
 System.out.print(" --> " + name);
 }
 System.out.println("\n");
 }
}
public static void main(String[] args) {
 DirectedCycle graph = new DirectedCycle();
 graph.print();
 }
}

My program above doesn't have yet a function that checks cycle and also I want to implement the root node thing.. If anyone can improve my program above just answer me and give me some code I can rely. Thanks! (I'm beginner!)

• Anubian Noob: You're doing great! This isn't a site for people to write code for you, so you might encounter some community negativity. Good luck!
• Rajind Ruparathna: stackoverflow.com/questions/2663115/…

Answer 1

The most efficient way to detect a cycle in Floyd's Cycle detection algo., which is basically moving two pointers over the linked list, one moving at normal one step at a time slow pointer and the other with double the speed of the slow pointer, i.e fast pointer.

Java code for the same.

boolean detectloop(Node list) {
 if(list == null) 
 return false;
 Node slow, fast; 
 slow = fast = list; 
 while(true) {
 slow = slow.next; 
 if(fast.next != null)
 fast = fast.next.next; 
 else
 return false;
 if(slow == null || fast == null) 
 return false;
 if(slow == fast)
 return true;
 }
}

Answer 2

To check a cycle of a linked list, you want to iterate though with two different pointers, one moving through the list twice as fast. If there is a cycle, it will eventually be detected using this method. Also, for the end condition, you can check to see if all nodes have been visited, and if so, there is no cycle.