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:
Apache Commons Collections SetUtils
Java Program to Implement Bresenham Line Algorithm
Understanding Memory Leaks in Java
Finding the Eulerian path in $O(M)$
Giới thiệu Google Guice – Aspect Oriented Programming (AOP)
Lập trình đa luồng với CompletableFuture trong Java 8
Guide to the Java Queue Interface
Introduction to Apache Commons Text
Java Program to Check the Connectivity of Graph Using DFS
Guide to java.util.concurrent.Future
The Order of Tests in JUnit
Guide to CountDownLatch in Java
The XOR Operator in Java
Introduction to Spring Data JDBC
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java
Java Program to Implement Bit Array
The Difference Between map() and flatMap()
Java Program to Implement Find all Forward Edges in a Graph
Spring Boot - Web Socket
An Intro to Spring Cloud Vault
Encode a String to UTF-8 in Java
Introduction to Spring Cloud Netflix – Eureka
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java Convenience Factory Methods for Collections
Hướng dẫn Java Design Pattern – Strategy
Java Program to Describe the Representation of Graph using Adjacency Matrix
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Spring Cloud – Securing Services
Java Program to Implement vector
A Guide to Apache Commons Collections CollectionUtils
Java Program to Implement Unrolled Linked List
Kiểu dữ liệu Ngày Giờ (Date Time) trong java