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 Undirected 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 UndirectedEulerPath { private int[][] adjacencyMatrix; private int numberOfNodes; public UndirectedEulerPath(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; } } } DirectedEulerianCircuit path = new DirectedEulerianCircuit(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 UndirectedEulerPath.java $ java UndirectedEulerPath 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:
Java Program to Implement Regular Falsi Algorithm
Spring Cloud Series – The Gateway Pattern
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Spring MVC Content Negotiation
The StackOverflowError in Java
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Java Program to Represent Graph Using Incidence Matrix
Java Program to Compare Binary and Sequential Search
Java 8 Stream findFirst() vs. findAny()
Creating a Custom Starter with Spring Boot
Apache Commons Collections SetUtils
Tìm hiểu về Web Service
Spring MVC Tutorial
Functional Interfaces in Java 8
Java Program to Implement Bit Array
Java Program to Implement Dijkstra’s Algorithm using Set
HandlerAdapters in Spring MVC
Map Serialization and Deserialization with Jackson
Spring Security Custom AuthenticationFailureHandler
New Features in Java 9
Lớp TreeMap trong Java
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
A Guide to Java HashMap
Configure a RestTemplate with RestTemplateBuilder
Consumer trong Java 8
Jackson – Decide What Fields Get Serialized/Deserialized
Debug a JavaMail Program
Java Program to Implement Ternary Search Tree
Java Program to Implement Cubic convergence 1/pi Algorithm
Deploy a Spring Boot WAR into a Tomcat Server