This Java program,performs the DFS traversal on the given graph represented by a adjacency matrix to check for cycles in the graph.the DFS traversal makes use of an stack.
Here is the source code of the Java program to check for cycle in graph.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 CheckCycle
{
private Stack<Integer> stack;
private int adjacencyMatrix[][];
public CheckCycle()
{
stack = new Stack<Integer>();
}
public void dfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix.length - 1;
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++)
{
adjacencyMatrix[sourcevertex][destinationvertex] =
adjacency_matrix[sourcevertex][destinationvertex];
}
}
int visited[] = new int[number_of_nodes + 1];
int element = source;
int destination = source;
visited = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.peek();
destination = element;
while (destination <= number_of_nodes)
{
if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
{
if (stack.contains(destination))
{
System.out.println("The Graph contains cycle");
return;
}
}
if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
{
stack.push(destination);
visited[destination] = 1;
adjacencyMatrix[element][destination] = 0;
element = destination;
destination = 1;
continue;
}
destination++;
}
stack.pop();
}
}
public static void main(String...arg)
{
int number_of_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
CheckCycle checkCycle = new CheckCycle();
checkCycle.dfs(adjacency_matrix, source);
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
$javac CheckCycle.java $java CheckCycle Enter the number of nodes in the graph 5 Enter the adjacency matrix 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 Enter the source for the graph 1 The Graph contains a cycle
Related posts:
Giới thiệu JDBC Connection Pool
Ways to Iterate Over a List in Java
Quick Intro to Spring Cloud Configuration
Lớp LinkedHashMap trong Java
Programmatic Transaction Management in Spring
CyclicBarrier in Java
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
String Processing with Apache Commons Lang 3
Spring Cloud – Tracing Services with Zipkin
Running Spring Boot Applications With Minikube
Removing Elements from Java Collections
Spring WebClient Filters
Guide to the Synchronized Keyword in Java
Java TreeMap vs HashMap
Java Program to Implement the Monoalphabetic Cypher
Spring NoSuchBeanDefinitionException
Using Optional with Jackson
Transactions with Spring and JPA
Một số nguyên tắc, định luật trong lập trình
Remove the First Element from a List
Enum trong java
Request Method Not Supported (405) in Spring
Java Program to Implement Stack using Linked List
Java Program to Implement Threaded Binary Tree
Getting Started with Forms in Spring MVC
Display Auto-Configuration Report in Spring Boot
Graph Data Stucture
Guide to Java 8 groupingBy Collector
Java Program to Implement Fenwick Tree
Send email with JavaMail
Custom Thread Pools In Java 8 Parallel Streams
Java Program to Implement Quick Hull Algorithm to Find Convex Hull