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:
Spring REST API + OAuth2 + Angular
Spring’s RequestBody and ResponseBody Annotations
So sánh Array và ArrayList trong Java
Java InputStream to String
Using a Mutex Object in Java
Java Program to Check whether Graph is Biconnected
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Spring Webflux with Kotlin
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Guide To CompletableFuture
Java Program to Implement Graham Scan Algorithm to Find the Convex Hull
Java Program to Implement the Hill Cypher
Serverless Functions with Spring Cloud Function
Java Program to Implement Sieve Of Eratosthenes
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Marker Interface trong Java
A Guide to JUnit 5 Extensions
Overview of Spring Boot Dev Tools
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Java Program to Implement Strassen Algorithm
Guide to Character Encoding
Java Program to Represent Graph Using 2D Arrays
Tính đa hình (Polymorphism) trong Java
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Java Program to Implement ConcurrentLinkedQueue API
Introduction to Spring Data MongoDB
Spring JDBC
Java Stream Filter with Lambda Expression
Hướng dẫn sử dụng Printing Service trong Java
A Guide to Java HashMap
A Guide to ConcurrentMap