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:
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Find Transitive Closure of a Graph
Converting a Stack Trace to a String in Java
Spring Boot Integration Testing with Embedded MongoDB
Batch Processing with Spring Cloud Data Flow
Intro to Spring Boot Starters
Spring AMQP in Reactive Applications
Entity To DTO Conversion for a Spring REST API
Java Program to Implement CopyOnWriteArrayList API
Spring Boot - Flyway Database
So sánh ArrayList và Vector trong Java
Jackson – Bidirectional Relationships
Jackson Ignore Properties on Marshalling
Why String is Immutable in Java?
DynamoDB in a Spring Boot Application Using Spring Data
RegEx for matching Date Pattern in Java
Spring Boot - Admin Client
Quick Guide to Spring Bean Scopes
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Unsatisfied Dependency in Spring
Quick Guide to the Java StringTokenizer
XML Serialization and Deserialization with Jackson
Java Program to Perform LU Decomposition of any Matrix
Java Program to Generate Random Numbers Using Multiply with Carry Method
Truyền giá trị và tham chiếu trong java
Introduction to Eclipse Collections
Spring Boot - Twilio
The DAO with JPA and Spring
Spring Security Login Page with React
Custom Cascading in Spring Data MongoDB
Annotation trong Java 8
So sánh HashMap và Hashtable trong Java