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:
More Jackson Annotations
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Implement Hash Tables with Linear Probing
Tính đa hình (Polymorphism) trong Java
Intro to the Jackson ObjectMapper
Java Program to Implement Selection Sort
Java Program to Decode a Message Encoded Using Playfair Cipher
Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph
Jackson Unmarshalling JSON with Unknown Properties
A Guide to the Java LinkedList
New Features in Java 14
An Example of Load Balancing with Zuul and Eureka
Sorting Query Results with Spring Data
Using a Spring Cloud App Starter
Java Program to Check Cycle in a Graph using Graph traversal
Java Program to Implement Shunting Yard Algorithm
Java Program to Implement Shell Sort
Spring RequestMapping
Spring’s RequestBody and ResponseBody Annotations
Java Program to Implement Sparse Array
A Guide to JUnit 5 Extensions
Java Program to Implement Trie
Spring Cloud Series – The Gateway Pattern
Java Program to Implement Bit Array
Java Program to Implement WeakHashMap API
How to Get a Name of a Method Being Executed?
Sorting in Java
Java – Write to File
Java Program to Implement D-ary-Heap
Java Program to Implement Binomial Heap
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to Implement Shoelace Algorithm