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 Directed 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 DirectedEulerPath { private int[][] adjacencyMatrix; private int numberOfNodes; public DirectedEulerPath(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(); } } DirectedEulerPath path = new DirectedEulerPath(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 DirectedEulerPath.java $ java DirectedEulerPath 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:
Call Methods at Runtime Using Java Reflection
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Implement Shell Sort
Custom Exception trong Java
Dockerizing a Spring Boot Application
Exception Handling in Java
Spring WebClient Requests with Parameters
More Jackson Annotations
Java Program to Implement AVL Tree
Java Program to Find a Good Feedback Edge Set in a Graph
Java Program to find the maximum subarray sum using Binary Search approach
Chương trình Java đầu tiên
Java Program to Implement Min Heap
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Java Program to Implement Hash Tree
How to Read HTTP Headers in Spring REST Controllers
Testing an OAuth Secured API with Spring MVC
Java Program to Implement Min Hash
Hướng dẫn Java Design Pattern – Proxy
Java Program to Find the Minimum value of Binary Search Tree
Chuyển đổi giữa các kiểu dữ liệu trong Java
Java Program to Implement Horner Algorithm
HttpAsyncClient Tutorial
Encode/Decode to/from Base64
Send an email with an attachment
Java Program to Implement Range Tree
Java – Random Long, Float, Integer and Double
Logout in an OAuth Secured Application
Java Program to Implement ConcurrentSkipListMap API
Java Program to Implement WeakHashMap API
Java Program to Implement Radix Sort
Java Program to Evaluate an Expression using Stacks