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:
Vector trong Java
Java Program to Find Hamiltonian Cycle in an UnWeighted Graph
Java Program to Implement Gale Shapley Algorithm
Spring Data – CrudRepository save() Method
Introduction to Project Reactor Bus
Hướng dẫn Java Design Pattern – Proxy
Java Program to Implement Hash Tables Chaining with Binary Trees
A Guide to JPA with Spring
Working With Maps Using Streams
Extract links from an HTML page
Java Program to Implement Euclid GCD Algorithm
Hướng dẫn Java Design Pattern – Abstract Factory
Introduction to Spring Data MongoDB
Testing an OAuth Secured API with Spring MVC
Prevent Cross-Site Scripting (XSS) in a Spring Application
Supplier trong Java 8
Compact Strings in Java 9
Java Program to Implement Range Tree
Java Program to Find the Vertex Connectivity of a Graph
Apache Camel with Spring Boot
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java – Reader to String
Guide to PriorityBlockingQueue in Java
Hướng dẫn Java Design Pattern – MVC
String Initialization in Java
Java Program to Implement Stack using Linked List
Extra Login Fields with Spring Security
Getting a File’s Mime Type in Java
Java – Delete a File
New Features in Java 15
Using a List of Values in a JdbcTemplate IN Clause
Using Spring @ResponseStatus to Set HTTP Status Code