Java Program to Check Cycle in a Graph using Topological Sort

This Java program,to perform the topological Sort on a given graph by the DFS method.The topological sort is performed on a directed acyclic graph.

Here is the source code of the Java program to check for cycle in topological sort. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
 
public class TopoCycle
{
    private Stack<Integer> stack;
 
    public TopoCycle() 
    {
        stack = new Stack<Integer>();
    }
 
    public boolean checkCycle(int adjacency_matrix[][], int source)
    {
        int number_of_nodes = adjacency_matrix.length - 1;
        int[] topological_sort = new int [number_of_nodes + 1];
        int pos = 1;
        int j;
        boolean cycle = false;
 
 
        int visited[] = new int[number_of_nodes + 1];
        int element = source;
        int i = source;
        visited = 1;
        stack.push(source);
 
 
        while (!stack.isEmpty())
        {
            element = stack.peek();
            while (i <= number_of_nodes)
            {
                if (adjacency_matrix[element][i] == 1 && visited[i] == 1)
                {
                    if (stack.contains(i))
                    {
                        System.out.println("The Graph Contains a cycle");
                        cycle = true; 
                        return cycle;
                    }
                }
                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
                {
                    stack.push(i);
                    visited[i] = 1;
                    element = i;
                    i = 1;
                    continue;
                }
                i++;
            }
            j = stack.pop();	
            topological_sort[pos++] = j;
            i = ++j;
        }
        System.out.println("The Graph does not Contain cycle");
        return cycle;
    }	
 
    public static void main(String...arg)
    {
        int number_no_nodes, source;
        Scanner scanner = null;
        try 
        {
            System.out.println("Enter the number of nodes in the graph");
            scanner = new Scanner(System.in);
            number_no_nodes = scanner.nextInt();
 
            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
            System.out.println("Enter the adjacency matrix");
	    for (int i = 1; i <= number_no_nodes; i++)
                for (int j = 1; j <= number_no_nodes; j++)
                    adjacency_matrix[i][j] = scanner.nextInt();
 
            System.out.println("Enter the source for the graph");
            source = scanner.nextInt();
 
	    TopoCycle topoCycle = new TopoCycle();
            topoCycle.checkCycle(adjacency_matrix, source);
 
        }catch(InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input format");
        }
        scanner.close();
    }
}
$javac TopoCycle.java
$java TopoCycle
Enter the number of nodes in the graph
5
Enter the adjacency matrix
0 1 0 1 0
0 0 1 0 0 
0 0 0 0 1
0 1 0 0 1
0 0 0 1 0 
Enter the source for the graph
1
The Graph contains a cycle

Related posts:

Finding articulation points in a graph in $O(N+M)$
Java Program to Implement Heap
Java – Combine Multiple Collections
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Convenience Factory Methods for Collections
Using a Mutex Object in Java
Java Program to Implement Merge Sort Algorithm on Linked List
A Guide to Spring Boot Admin
Java Program to Implement Hamiltonian Cycle Algorithm
Java Program to Implement Fermat Factorization Algorithm
OAuth 2.0 Resource Server With Spring Security 5
Java Concurrency Interview Questions and Answers
New Features in Java 15
Lớp Arrarys trong Java (Arrays Utility Class)
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Prevent Brute Force Authentication Attempts with Spring Security
So sánh HashMap và HashSet trong Java
How to Find an Element in a List with Java
Spring Boot - Web Socket
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Spring Boot Configuration with Jasypt
Java Program to Implement Fermat Primality Test Algorithm
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
New Features in Java 12
Java Program to Implement Triply Linked List
Form Validation with AngularJS and Spring MVC
Injecting Prototype Beans into a Singleton Instance in Spring
Java Program to Implement Best-First Search
Java Program to Implement Karatsuba Multiplication Algorithm
How To Serialize and Deserialize Enums with Jackson
Spring Data JPA @Query