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 an Directed Graph Contains a Eulerian Path. 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 DirectedEulerPath { private int[][] adjacencyMatrix; private int numberOfNodes; public DirectedEulerPath(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(); } } DirectedEulerPath path = new DirectedEulerPath(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 DirectedEulerPath.java $ java DirectedEulerPath Enter the number of nodes in the graph 4 Enter the adjacency matrix 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 As the graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.
Related posts:
What is Thread-Safety and How to Achieve it?
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Java Program to Implement Booth Algorithm
Marker Interface trong Java
Java Program to Implement PriorityBlockingQueue API
Java Program to add two large numbers using Linked List
Toán tử trong java
Java Program to Implement Cubic convergence 1/pi Algorithm
Một số nguyên tắc, định luật trong lập trình
Quick Guide on Loading Initial Data with Spring Boot
Guide to the Volatile Keyword in Java
RegEx for matching Date Pattern in Java
Spring Security – Reset Your Password
Easy Ways to Write a Java InputStream to an OutputStream
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Java Switch Statement
Introduction to the Java NIO Selector
Circular Dependencies in Spring
MyBatis with Spring
Java Program to Perform Quick Sort on Large Number of Elements
Java Program to Implement Interpolation Search Algorithm
Java Program to Implement Graph Structured Stack
Converting a Stack Trace to a String in Java
Control Structures in Java
Java Program to Implement EnumMap API
Java Program to Construct K-D Tree for 2 Dimensional Data
Model, ModelMap, and ModelAndView in Spring MVC
Convert XML to JSON Using Jackson
Spring MVC Async vs Spring WebFlux
The Guide to RestTemplate
Convert char to String in Java
Cơ chế Upcasting và Downcasting trong java