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!)

Answer 1

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.

Answer 2

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;
    }
}