Java Program to Implement Euler Circuit Problem

This Java program is Implement Euler Circuit Problem.In graph theory, an Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.

Here is the source code of the Java program to Implement Euler Circuit Problem. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

import java.util.InputMismatchException;

```
import java.util.Scanner;
```
```
 
```
```
public class EulerCircuit
```
```
{
```
```
 
```
```
    private int[][] adjacencyMatrix;
```
```
    private int numberOfNodes; 
```
```
 
```

    public EulerCircuit (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 oddDegreeVertex ()
```
```
    {
```
```
        int vertex = -1;
```

        for (int node = 1; node <= numberOfNodes; node++)

```
        {
```

            if ((degree(node) % 2) != 0)

```
            {
```
```
                vertex = node;
```
```
                break;
```
```
            }
```
```
        }
```
```
        return vertex;
```
```
    }
```
```
 
```

    public void printEulerTourUtil (int vertex)

```
    {
```

        for (int destination = 1; destination <= numberOfNodes; destination++)

```
        {
```

            if(adjacencyMatrix[vertex][destination] == 1 && isVaildNextEdge(vertex, destination))

```
            {
```

                System.out.println(" source : " + vertex + " destination " + destination);

                removeEdge(vertex, destination);

                printEulerTourUtil(destination);

```
            }	
```
```
        }
```
```
    }
```
```
 
```
```
    public void printEulerTour ()
```
```
    {
```
```
        int vertex = 1;
```
```
        if (oddDegreeVertex() != -1)
```
```
        {
```
```
            vertex = oddDegreeVertex();
```
```
        }
```
```
        printEulerTourUtil(vertex);
```
```
        return;
```
```
    }
```
```
 
```

    public boolean isVaildNextEdge (int source, int destination)

```
    {
```
```
        int count = 0;
```

        for (int vertex = 1; vertex <= numberOfNodes; vertex++)

```
        {
```

            if (adjacencyMatrix[source][vertex] == 1)

```
            {
```
```
                count++;
```
```
            }
```
```
        }
```
```
 
```
```
        if (count == 1 )
```
```
        {   
```
```
            return true;
```
```
        }
```
```
 
```

        int visited[] = new int[numberOfNodes + 1];

        int count1 = DFSCount(source, visited);

```
 
```

        removeEdge(source, destination);

        for (int vertex = 1; vertex <= numberOfNodes; vertex++)

```
        {
```
```
            visited[vertex] = 0;
```
```
        }
```
```
 
```

       int count2 = DFSCount(source, visited);

```
       addEdge(source, destination);
```
```
 
```

       return (count1 > count2 ) ? false : true;

```
    } 
```
```
 
```

    public int DFSCount (int source, int visited[])

```
    {
```
```
        visited[source] = 1;
```
```
        int count = 1;
```
```
        int destination = 1;
```
```
 
```

        while (destination <= numberOfNodes)

```
        {
```

            if(adjacencyMatrix[source][destination] == 1 && visited[destination] == 0)

```
            {
```

                count += DFSCount(destination, visited);

```
            }
```
```
            destination++;
```
```
        }
```
```
        return count;
```
```
    }
```
```
 
```

    public void removeEdge (int source, int destination)

```
    {
```

        adjacencyMatrix[source][destination]  = 0;

        adjacencyMatrix[destination][source] = 0;

```
    }
```
```
 
```

    public void addEdge (int source, int destination)

```
    {
```

        adjacencyMatrix[source][destination] = 1;

        adjacencyMatrix[destination][source] = 1;

```
    }
```
```
 
```

    public static void main (String... arg)

```
    {
```
```
        int number_of_nodes;
```
```
        Scanner scanner = null;
```
```
 
```
```
        try
```
```
        {
```
```
            // read the number of nodes
```

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_of_nodes = scanner.nextInt();

```
 
```

            // read the adjacency matrix

            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;

```
                    }
```
```
                }
```
```
            }			
```

            System.out.println("the euler path or euler circuit is ");

            // print euler path or circuit

            EulerCircuit circuit = new EulerCircuit(number_of_nodes, adjacency_matrix);

```
            circuit.printEulerTour();
```

        } catch (InputMismatchException inputMismatch)

```
         {
```

             System.out.println("Wrong Input format");

```
         }
```
```
        scanner.close();
```
```
    }	
```
```
}
```

$javac EulerCircuit.java
$java EulerCircuit
Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
the euler path or euler circuit is 
 source : 1 destination 2
 source : 2 destination 3
 source : 3 destination 4
 source : 4 destination 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Implement Max-Flow Min-Cut Theorem

» Next - Java Program to Implement Traveling Salesman Problem using Nearest Neighbour Algorithm

Related Posts:

Recommended Articles: