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 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 UndirectedEulerianCircuit { private int[][] adjacencyMatrix; private int numberOfNodes; public UndirectedEulerianCircuit(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 UndirectedEulerianCircuit.java $ java UndirectedEulerianCircuit Enter the number of nodes in the graph 6 Enter the adjacency matrix 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 As the graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.
Related posts:
Java Program to Compute DFT Coefficients Directly
Spring Boot Configuration with Jasypt
Java Program to implement Array Deque
An Introduction to Java.util.Hashtable Class
Java Program to Implement ScapeGoat Tree
Java Program to Implement Skew Heap
Java Program to Implement Shoelace Algorithm
Java Program to Find a Good Feedback Edge Set in a Graph
Java Program to Represent Graph Using 2D Arrays
A Guide to ConcurrentMap
Initialize a HashMap in Java
Introduction to Spring Security Expressions
Giới thiệu Json Web Token (JWT)
A Guide to System.exit()
Java – Rename or Move a File
Biểu thức Lambda trong Java 8 – Lambda Expressions
Java Program to Implement Hash Tables with Linear Probing
A Guide to Concurrent Queues in Java
Java Program to Implement Meldable Heap
Hướng dẫn sử dụng Java Annotation
Sử dụng CyclicBarrier trong Java
How to use the Spring FactoryBean?
Spring Data JPA @Query
Java Program to Implement Hash Tree
Java Program to Implement Circular Doubly Linked List
Spring Boot - Enabling HTTPS
Spring Boot - Web Socket
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Sắp xếp trong Java 8
Java Program to Implement Heap
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
ExecutorService – Waiting for Threads to Finish