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:
HashMap trong Java hoạt động như thế nào?
Jackson – Unmarshall to Collection/Array
Configure a Spring Boot Web Application
Java Program to Implement Counting Sort
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Remove the First Element from a List
Spring Webflux and CORS
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Spring Cloud AWS – Messaging Support
Hướng dẫn Java Design Pattern – Proxy
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Model, ModelMap, and ModelAndView in Spring MVC
Multi Dimensional ArrayList in Java
Giới thiệu SOAP UI và thực hiện test Web Service
Java Program to Implement Singly Linked List
Spring Data MongoDB Transactions
Java Program to Perform Finite State Automaton based Search
Spring Security Form Login
Java Program to Implement Min Heap
Spring Boot - Thymeleaf
Java Program to Implement Regular Falsi Algorithm
Java Program to Perform Partial Key Search in a K-D Tree
HttpAsyncClient Tutorial
Spring Boot - Web Socket
Sorting Query Results with Spring Data
Java Program to Implement Insertion Sort
Java Program to Implement PriorityQueue API
Java 8 Collectors toMap
Java Program to Implement Binomial Tree
Java Program to Implement LinkedHashSet API
Java Program to Implement Circular Doubly Linked List