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:
Spring 5 Testing with @EnabledIf Annotation
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Hướng dẫn sử dụng Java Generics
Spring RestTemplate Error Handling
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Spring WebClient Requests with Parameters
Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence
Java Program to Implement Suffix Tree
Java Program to Find Transitive Closure of a Graph
Java Program to Implement Min Heap
String Joiner trong Java 8
Spring Cloud AWS – RDS
Java Program to Check Cycle in a Graph using Topological Sort
Inject Parameters into JUnit Jupiter Unit Tests
Java Program to Create the Prufer Code for a Tree
Guide To CompletableFuture
Hướng dẫn Java Design Pattern – Singleton
Java Program to Implement Direct Addressing Tables
Java Program to Check whether Graph is a Bipartite using DFS
Java Program to Find the Connected Components of an UnDirected Graph
4 tính chất của lập trình hướng đối tượng trong Java
Getting Started with Forms in Spring MVC
Java String to InputStream
Các kiểu dữ liệu trong java
Connect through a Proxy
Spring MVC + Thymeleaf 3.0: New Features
String Operations with Java Streams
Java Program to implement Dynamic Array
Java Program to Check the Connectivity of Graph Using DFS
Java – Reader to String
Constructor Dependency Injection in Spring
Guide to @ConfigurationProperties in Spring Boot