Java Program to Check Whether a Directed Graph Contains a Eulerian Path

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:

Query Entities by Dates and Times with Spring Data JPA
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Hướng dẫn Java Design Pattern – Template Method
What is a POJO Class?
Introduction to Project Reactor Bus
Java Program to Implement Borwein Algorithm
Java Program to Implement Sieve Of Eratosthenes
Java Program to Generate a Random Subset by Coin Flipping
Java Program to Implement Find all Cross Edges in a Graph
Spring Boot - Interceptor
Cachable Static Assets with Spring MVC
Java Program to Implement Adjacency List
Hướng dẫn sử dụng String Format trong Java
Java 14 Record Keyword
Convert Time to Milliseconds in Java
New in Spring Security OAuth2 – Verify Claims
Java Program to Implement Hash Tree
Spring Data Reactive Repositories with MongoDB
Java Program to Implement Stack
Java Program to Create a Random Graph Using Random Edge Generation
Quick Guide to Spring Controllers
Java Program to Emulate N Dice Roller
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Java Program to Implement the Bin Packing Algorithm
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Guide to Java 8’s Collectors
Java – Reader to InputStream
Java Program to Solve any Linear Equation in One Variable
Introduction to Spring Method Security
Java Program to Find a Good Feedback Edge Set in a Graph
Java Program to Generate Random Partition out of a Given Set of Numbers or Characters
Java Program to Perform the Unique Factorization of a Given Number