Java Program to Check Whether an Undirected 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 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:

Java Program to Implement Knapsack Algorithm
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Java Program to Implement Lloyd’s Algorithm
Creating a Web Application with Spring 5
Tips for dealing with HTTP-related problems
Sử dụng CountDownLatch trong Java
Spring Boot - Database Handling
Registration with Spring Security – Password Encoding
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Java Program to Implement Gabow Algorithm
Java Program to Represent Graph Using 2D Arrays
Java Program to Implement Aho-Corasick Algorithm for String Matching
Ép kiểu trong Java (Type casting)
Vòng lặp for, while, do-while trong Java
Hướng dẫn Java Design Pattern – Composite
DistinctBy in the Java Stream API
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
Java Program to Find Whether a Path Exists Between 2 Given Nodes
Java Program to Implement Patricia Trie
@Order in Spring
Java Program to Implement Max Heap
Java – Write an InputStream to a File
TreeSet và sử dụng Comparable, Comparator trong java
Java Program to Implement Gaussian Elimination Algorithm
Java Program to Implement Strassen Algorithm
Introduction to the Functional Web Framework in Spring 5
Java Program to Generate Randomized Sequence of Given Range of Numbers
Java Program to Check for balanced parenthesis by using Stacks
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Luồng Daemon (Daemon Thread) trong Java
Introduction to Spring MVC HandlerInterceptor