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:
Guide to Escaping Characters in Java RegExps
ETL with Spring Cloud Data Flow
Configure a Spring Boot Web Application
So sánh HashMap và HashSet trong Java
Spring Autowiring of Generic Types
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Java Program to Implement Stack using Linked List
Hướng dẫn Java Design Pattern – Decorator
Một số ký tự đặc biệt trong Java
Compact Strings in Java 9
Java – Generate Random String
Send email with SMTPS (eg. Google GMail)
Refactoring Design Pattern với tính năng mới trong Java 8
Guide to the Java ArrayList
A Guide to the finalize Method in Java
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Java Program to Find Inverse of a Matrix
Exploring the Spring 5 WebFlux URL Matching
Assertions in JUnit 4 and JUnit 5
Toán tử instanceof trong java
Introduction to Using Thymeleaf in Spring
Guide to the ConcurrentSkipListMap
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Perform Stooge Sort
Spring Cloud – Adding Angular
Java Program to Check Multiplicability of Two Matrices
Pagination and Sorting using Spring Data JPA
So sánh HashMap và Hashtable trong Java
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Java Program to Find Number of Articulation points in a Graph
So sánh Array và ArrayList trong Java
Spring Cloud Series – The Gateway Pattern