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[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 = 1; int count = 1; int destination = 1; while (destination <= numberOfNodes) { if(adjacencyMatrix[destination] == 1 && visited[destination] == 0) { count += DFSCount(destination, visited); } destination++; } return count; } public void removeEdge (int source, int destination) { adjacencyMatrix[destination] = 0; adjacencyMatrix[destination] = 0; } public void addEdge (int source, int destination) { adjacencyMatrix[destination] = 1; adjacencyMatrix[destination] = 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
Related posts:
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Java Program to Show the Duality Transformation of Line and Point
Guide to @JsonFormat in Jackson
Java Program to Perform Addition Operation Using Bitwise Operators
Chuyển đổi giữa các kiểu dữ liệu trong Java
Compact Strings in Java 9
Integer Constant Pool trong Java
Hướng dẫn sử dụng Printing Service trong Java
Một số ký tự đặc biệt trong Java
Java Program to Implement Strassen Algorithm
How to Implement Caching using Adonis.js 5
Java Program to Implement JobStateReasons API
Java Convenience Factory Methods for Collections
Introduction to Spring Cloud Rest Client with Netflix Ribbon
Lớp TreeMap trong Java
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Java Program to Implement Nth Root Algorithm
Java Program to implement Circular Buffer
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Checking for Empty or Blank Strings in Java
Java Program to Implement Jarvis Algorithm
Finding the Differences Between Two Lists in Java
Simple Single Sign-On with Spring Security OAuth2
Introduction to Using FreeMarker in Spring MVC
Java Program to Emulate N Dice Roller
Spring Boot - Tomcat Deployment
Spring Security – Reset Your Password
An Intro to Spring Cloud Vault
Debug a JavaMail Program
New Features in Java 8
Life Cycle of a Thread in Java
Introduction to Spring Cloud Netflix – Eureka