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 a Directed 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 DirectedEulerianCircuit { private int[][] adjacencyMatrix; private int numberOfNodes; public DirectedEulerianCircuit(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 DirectedEulerianCircuit.java $ java DirectedEulerianCircuit Enter the number of nodes in the graph 6 Enter the adjacency matrix 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 As the graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.
Related posts:
Write/Read cookies using HTTP and Read a file from the internet
Limiting Query Results with JPA and Spring Data JPA
Jackson vs Gson
Hamcrest Collections Cookbook
Spring Boot - Tracing Micro Service Logs
Java Program to Find kth Largest Element in a Sequence
Setting a Request Timeout for a Spring REST API
Java Program to Implement CopyOnWriteArraySet API
Vòng lặp for, while, do-while trong Java
Function trong Java 8
Quick Guide to Spring Controllers
Logout in an OAuth Secured Application
Bootstrapping Hibernate 5 with Spring
Java Program to Implement Sorted List
Check If a File or Directory Exists in Java
Quick Guide to Spring Bean Scopes
Java Program to Represent Graph Using Adjacency List
Spring Data JPA @Query
How to Break from Java Stream forEach
Java NIO2 Path API
Java Program to Check whether Graph is a Bipartite using DFS
How to Convert List to Map in Java
Apache Camel with Spring Boot
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Getting Started with Stream Processing with Spring Cloud Data Flow
Spring REST with a Zuul Proxy
Java Program to Generate Randomized Sequence of Given Range of Numbers
Using a List of Values in a JdbcTemplate IN Clause
Sử dụng CountDownLatch trong Java
Java – Reader to String
Use Liquibase to Safely Evolve Your Database Schema