Eulerian and Hamiltonian Paths
In graph theory, an Eulerian path is a path in a graph that visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.
Similarly, a Hamiltonian path is a path in a graph that visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex.
Eulerian and Hamiltonian paths are important concepts in graph theory and have applications in various areas, such as transportation planning, network optimization, and DNA sequencing.
To find an Eulerian path or Eulerian circuit in a graph, we can use the Hierholzer's algorithm. This algorithm starts from an arbitrary vertex and repeatedly adds edges to the current path until all edges have been visited.
Here's an example of Java code that finds an Eulerian path in a graph:
1// Example code for finding an Eulerian path in a graph
2int[][] graph = {
3 {0, 1, 1, 1, 0},
4 {1, 0, 1, 0, 1},
5 {1, 1, 0, 1, 0},
6 {1, 0, 1, 0, 1},
7 {0, 1, 0, 1, 0}
8};
9
10int[] path = new int[graph.length];
11for (int i = 0; i < path.length; i++) {
12 path[i] = -1;
13}
14
15// Starting vertex
16int startVertex = 0;
17
18// Call the function to find an Eulerian path
19findEulerianPath(graph, path, startVertex);
20
21// Print the Eulerian path
22System.out.println("Eulerian Path:");
23for (int i = 0; i < path.length; i++) {
24 System.out.print(path[i] + " ");
25}
26
27// Function to find an Eulerian path
28private static void findEulerianPath(int[][] graph, int[] path, int currVertex) {
29 // Loop through all vertices
30 for (int nextVertex = 0; nextVertex < graph.length; nextVertex++) {
31 // Check if an edge exists between the current vertex and the next vertex
32 if (graph[currVertex][nextVertex] == 1) {
33 // Check if the next vertex is not visited already
34 if (path[nextVertex] == -1) {
35 // Set current vertex and next vertex as visited
36 path[nextVertex] = currVertex;
37
38 // Recursively find the Eulerian path for the next vertex
39 findEulerianPath(graph, path, nextVertex);
40
41 // Check if all vertices are visited and there is an edge from the last vertex to the starting vertex
42 if (isLastEdge(graph, currVertex, nextVertex) && isAllVisited(path)) {
43 // Set the last vertex as the next vertex
44 path[0] = nextVertex;
45 }
46 }
47 }
48 }
49}
50
51// Function to check if the current vertex has an edge to the next vertex
52private static boolean isLastEdge(int[][] graph, int currVertex, int nextVertex) {
53 // Get the degree of the current vertex
54 int currVertexDegree = 0;
55 for (int i = 0; i < graph.length; i++) {
56 currVertexDegree += graph[currVertex][i];
57 }
58
59 // If the degree is 1, it is the last edge
60 return currVertexDegree == 1;
61}
62
63// Function to check if all vertices are visited
64private static boolean isAllVisited(int[] path) {
65 for (int i = 0; i < path.length; i++) {
66 if (path[i] == -1) {
67 return false;
68 }
69 }
70 return true;
71}xxxxxxxxxx}class Main { public static void main(String[] args) { // replace with your Java logic here // Example code for Eulerian and Hamiltonian Paths int[][] graph = { {0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 0} }; int[] path = new int[graph.length]; for (int i = 0; i < path.length; i++) { path[i] = -1; } // Starting vertex int startVertex = 0; // Call the function to find an Eulerian path findEulerianPath(graph, path, startVertex); // Print the Eulerian path System.out.println("Eulerian Path:"); for (int i = 0; i < path.length; i++) { System.out.print(path[i] + " "); } }