This Java program demonstrates how to detect cycles in a directed graph using the Depth First Search (DFS) algorithm. Cycle detection is important for determining if certain processes, such as task scheduling or package dependency resolutions, can proceed without conflicts.

Java Code

import java.util.*;

class Graph {
    private final int V;   // No. of vertices
    private final List<List> adj; // Adjacency list

    Graph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; ++i)
            adj.add(new ArrayList<>());
    }

    void addEdge(int source, int dest) {
        adj.get(source).add(dest); // Add edge from source to destination
    }

    boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) {
        if (recStack[i])
            return true;
        if (visited[i])
            return false;

        visited[i] = true;
        recStack[i] = true;
        List children = adj.get(i);

        for (Integer c: children)
            if (isCyclicUtil(c, visited, recStack))
                return true;

        recStack[i] = false;
        return false;
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];
        
        for (int i = 0; i < V; i++)
            if (isCyclicUtil(i, visited, recStack))
                return true;

        return false;
    }
}

public class CycleDetection {
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        if (graph.isCyclic())
            System.out.println("Graph contains a cycle");
        else
            System.out.println("Graph does not contain a cycle");
    }
}

Explanation of the Code

The program is structured as follows:

• Graph Class: This class encapsulates the representation of a directed graph using an adjacency list. Methods include adding edges and checking for cycles.
• addEdge Method: Adds a directed edge from a source vertex to a destination vertex.
• isCyclic Method: Public method that initializes necessary arrays and checks for cycles starting from each vertex not yet visited.
• isCyclicUtil Method: A recursive method that uses a depth-first search approach to explore all possible paths from the current vertex. It uses a recursion stack to keep track of vertices that are in the current recursion stack of the DFS. If a vertex is encountered again in the current path, a cycle is detected.

This method of cycle detection is efficient and fundamental in ensuring that directed graphs used in various computational and real-world applications are acyclic before proceeding with tasks that require a cycle-free environment.