This is a java program to check whether graph contains Eulerian Cycle. The criteran Euler suggested,
1. If graph has no odd degree vertex, there is at least one Eulerian Circuit.
2. If graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.
3. If graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.
Here is the source code of the Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; import java.util.InputMismatchException; import java.util.Scanner; public class DirectedEulerianCircuit { private int[][] adjacencyMatrix; private int numberOfNodes; public DirectedEulerianCircuit(int numberOfNodes, int[][] adjacencyMatrix) { this.numberOfNodes = numberOfNodes; this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1]; for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++) { this.adjacencyMatrix[sourceVertex][destinationVertex] = adjacencyMatrix[sourceVertex][destinationVertex]; } } } public int degree(int vertex) { int degree = 0; for (int destinationvertex = 1; destinationvertex <= numberOfNodes; destinationvertex++) { if (adjacencyMatrix[vertex][destinationvertex] == 1 || adjacencyMatrix[destinationvertex][vertex] == 1) { degree++; } } return degree; } public int countOddDegreeVertex() { int count = 0; for (int node = 1; node <= numberOfNodes; node++) { if ((degree(node) % 2) != 0) { count++; } } return count; } public static void main(String... arg) { int number_of_nodes; 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(); } } // make the graph undirected for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) { adjacency_matrix[j][i] = 1; } } } UndirectedEulerPath path = new UndirectedEulerPath(number_of_nodes, adjacency_matrix); int count = path.countOddDegreeVertex(); if (count == 0) { System.out .println("As the graph has no odd degree vertex, there is at least one Eulerian Circuit."); } else if (count == 2) { System.out .println("As the graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path."); } else { System.out .println("As the graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path."); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
Output:
$ javac DirectedEulerianCircuit.java $ java DirectedEulerianCircuit Enter the number of nodes in the graph 6 Enter the adjacency matrix 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 As the graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.
Related posts:
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Lớp lồng nhau trong java (Java inner class)
The Registration Process With Spring Security
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Spring – Injecting Collections
Cachable Static Assets with Spring MVC
Jackson – Decide What Fields Get Serialized/Deserialized
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Configure a RestTemplate with RestTemplateBuilder
Introduction to Netflix Archaius with Spring Cloud
Spring Security Login Page with React
Join and Split Arrays and Collections in Java
Java Program to Find Transitive Closure of a Graph
Binary Numbers in Java
Java Program to Implement PriorityQueue API
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
RestTemplate Post Request with JSON
Guide to the Volatile Keyword in Java
Introduction to the Java ArrayDeque
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Map to String Conversion in Java
Java Program to Find the Connected Components of an UnDirected Graph
Java Program to Implement Gauss Seidel Method
Generating Random Numbers in a Range in Java
Server-Sent Events in Spring
Introduction to Spring Data JPA
Java Program to Implement Regular Falsi Algorithm
Spring Cloud – Adding Angular
How to use the Spring FactoryBean?
Count Occurrences of a Char in a String
Spring Webflux and CORS
Primitive Type Streams in Java 8