The task of the Chinese postman. Finding the Euler cycle
At the university, they were asked to solve the problem of the Chinese postman.Here is the algorithm for solving it.
-
We look at whether the graph is Eulerian or not. If yes, go to point (5).
-
We construct a distance matrix for graphs with odd degrees of vertices.
-
We build minimal matching pairs.
-
We build imaginary paths for the found pairs.Now our graph is Eulerian.
-
We find the Euler cycle and this will be the answer in our tasks. The problem with point 5 is if the graph was originally non-Eulerian. Outputs a path that is not clear to me. I tried to find the error myself, but nothing came out. I set the adjacency matrix as
0 1 1 0
1 0 1 1
1 1 0 2
0 2 1 0
Where numbers greater than 0 indicate the number of paths, including imaginary ones.With this matrix, the values 01133210private List<Integer> eilerPath(int[][] matrixAdjacency) { Stack<Integer> stack = new Stack<>(); List<Integer> list = new ArrayList<>(); int v = 0; int u; int edge; stack.push(v); while (!stack.empty()) { edge = findAdjacencyVertex(matrixAdjacency, stack.peek()); if (edge == -1) { list.add(stack.pop()); } else { u = edge; matrixAdjacency[stack.peek()][u]--; matrixAdjacency[u][stack.peek()]--; stack.push(u); } } return list; } private int findAdjacencyVertex(int[][] matrixAdjacency, int edge) { for (int i = 0; i < matrixAdjacency.length; i++) { if (matrixAdjacency[edge][i] > 0) { return i; } } return -1; }
1 answers
The algorithm is fully working. I found an error in another part of the code. The adjacency matrix with imaginary paths was not constructed quite correctly. In some places, I simply did not add them, which resulted in paths with an odd number of edges.