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 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 UndirectedEulerianCircuit
{
private int[][] adjacencyMatrix;
private int numberOfNodes;
public UndirectedEulerianCircuit(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 UndirectedEulerianCircuit.java $ java UndirectedEulerianCircuit Enter the number of nodes in the graph 6 Enter the adjacency matrix 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 As the graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.
Related posts:
Java Program to Implement Graph Structured Stack
Spring Boot - Building RESTful Web Services
Autoboxing và Unboxing trong Java
How to Get All Dates Between Two Dates?
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Jackson Date
Convert String to int or Integer in Java
Comparing Dates in Java
HttpClient 4 Cookbook
Spring Security OAuth2 – Simple Token Revocation
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Java Program to Find Minimum Element in an Array using Linear Search
Create Java Applet to Simulate Any Sorting Technique
Java Program to Create a Random Linear Extension for a DAG
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Introduction to the Java ArrayDeque
Java – Reader to InputStream
HttpAsyncClient Tutorial
Extra Login Fields with Spring Security
Java Program to Find the Vertex Connectivity of a Graph
Converting Iterator to List
Registration – Password Strength and Rules
A Guide to ConcurrentMap
Hướng dẫn Java Design Pattern – Memento
XML-Based Injection in Spring
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Default Password Encoder in Spring Security 5
Guide to Java Instrumentation
Sử dụng CountDownLatch trong Java
Java Program to Implement Fermat Factorization Algorithm
Registration with Spring Security – Password Encoding