Java Program to Check Whether an Undirected Graph Contains a Eulerian Cycle

«
»
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.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.InputMismatchException;
  5. import java.util.Scanner;
  6.  
  7. public class UndirectedEulerianCircuit
  8. {
  9.     private int[][] adjacencyMatrix;
  10.     private int     numberOfNodes;
  11.  
  12.     public UndirectedEulerianCircuit(int numberOfNodes, int[][] adjacencyMatrix)
  13.     {
  14.         this.numberOfNodes = numberOfNodes;
  15.         this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes + 1];
  16.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  17.         {
  18.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  19.             {
  20.                 this.adjacencyMatrix[sourceVertex][destinationVertex] = adjacencyMatrix[sourceVertex][destinationVertex];
  21.             }
  22.         }
  23.     }
  24.  
  25.     public int degree(int vertex)
  26.     {
  27.         int degree = 0;
  28.         for (int destinationvertex = 1; destinationvertex <= numberOfNodes; destinationvertex++)
  29.         {
  30.             if (adjacencyMatrix[vertex][destinationvertex] == 1
  31.                     || adjacencyMatrix[destinationvertex][vertex] == 1)
  32.             {
  33.                 degree++;
  34.             }
  35.         }
  36.         return degree;
  37.     }
  38.  
  39.     public int countOddDegreeVertex()
  40.     {
  41.         int count = 0;
  42.         for (int node = 1; node <= numberOfNodes; node++)
  43.         {
  44.             if ((degree(node) % 2) != 0)
  45.             {
  46.                 count++;
  47.             }
  48.         }
  49.         return count;
  50.     }
  51.  
  52.     public static void main(String... arg)
  53.     {
  54.         int number_of_nodes;
  55.         Scanner scanner = null;
  56.         try
  57.         {
  58.             System.out.println("Enter the number of nodes in the graph");
  59.             scanner = new Scanner(System.in);
  60.             number_of_nodes = scanner.nextInt();
  61.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  62.             System.out.println("Enter the adjacency matrix");
  63.             for (int i = 1; i <= number_of_nodes; i++)
  64.             {
  65.                 for (int j = 1; j <= number_of_nodes; j++)
  66.                 {
  67.                     adjacency_matrix[i][j] = scanner.nextInt();
  68.                 }
  69.             }
  70.             // make the graph undirected
  71.             for (int i = 1; i <= number_of_nodes; i++)
  72.             {
  73.                 for (int j = 1; j <= number_of_nodes; j++)
  74.                 {
  75.                     if (adjacency_matrix[i][j] == 1
  76.                             && adjacency_matrix[j][i] == 0)
  77.                     {
  78.                         adjacency_matrix[j][i] = 1;
  79.                     }
  80.                 }
  81.             }
  82.             UndirectedEulerPath path = new UndirectedEulerPath(number_of_nodes,
  83.                     adjacency_matrix);
  84.             int count = path.countOddDegreeVertex();
  85.             if (count == 0)
  86.             {
  87.                 System.out
  88.                         .println("As the graph has no odd degree vertex, there is at least one Eulerian Circuit.");
  89.             }
  90.             else if (count == 2)
  91.             {
  92.                 System.out
  93.                         .println("As the graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.");
  94.             }
  95.             else
  96.             {
  97.                 System.out
  98.                         .println("As the graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.");
  99.             }
  100.         }
  101.         catch (InputMismatchException inputMismatch)
  102.         {
  103.             System.out.println("Wrong Input format");
  104.         }
  105.         scanner.close();
  106.     }
  107. }

Output:

advertisement
$ 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.

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.