# Euler Paths with dfs algorithm problem

• March 22nd, 2012, 05:59 AM
claudio.r
Euler Paths with dfs algorithm problem
Hi everyone, it's my first time here ;)

I'm implementing an algorithm to find all the euler paths in a graph. I'm basing myself, to create the dfs, in the code found here: algorithm - Find all possible Euler cycles - Stack Overflow

Here is my current code:

Code :

```public class Graph {   private int numVertex; private int numEdges; private boolean[][] adj;   public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex+1][numVertex+1]; }   public void addEdge(int start, int end){ adj[start][end] = true; adj[end][start] = true; }   List<Integer> visited = new ArrayList<Integer>();   public Integer DFS(Graph G, int startVertex){ int i=0; pilha.push(startVertex); for(i=0; i<G.numVertex; i++){   if(G.adj[i][startVertex] != false){ System.out.println("i: " + i); G.adj[i][startVertex] = false; G.adj[startVertex][i] = false;   int c = pilha.pop();   visited.add(c); System.out.println("visited: " + visited);   DFS(G, i);   G.adj[i][startVertex] = true; G.adj[startVertex][i] = true; }   } return -1; }   Stack<Integer> pilha = new Stack();   public static void main(String[] args) {   Scanner input = new Scanner(System.in);   int numVertices = input.nextInt(); int numLinks = input.nextInt(); int startNode = input.nextInt();   Graph g = new Graph(numVertices, numLinks);   for(int i = 0; i<numLinks; i++){ g.addEdge(input.nextInt(),input.nextInt()); }   g.DFS(g, startNode); } }```

Unfortunately i don't get the right results and i can't seem to figure out why. I've tried a lot of thing as storing the results from the dfs in a list and print them, but still i got no paths.

any idea on how can i modify my code so i start getting the euler paths?
• March 22nd, 2012, 09:01 AM
andreas90
Re: Euler Paths with dfs algorithm problem
Quote:

Originally Posted by claudio.r
Unfortunately i don't get the right results and i can't seem to figure out why. I've tried a lot of thing as storing the results from the dfs in a list and print them, but still i got no paths.

any idea on how can i modify my code so i start getting the euler paths?

I think the problem is in your main() method but can you specify what's the expected and your current result?
• March 22nd, 2012, 09:29 AM
Norm
Re: Euler Paths with dfs algorithm problem
For testing can you make a main method that loads the Graph from the program without any user input required. That way everyone will be working with the same graph and testing will be faster without requiring user input.
• March 22nd, 2012, 11:36 AM
claudio.r
Re: Euler Paths with dfs algorithm problem
Here os the code with the main loading a graph. Currently it only makes a DFS search, i want to modify it to at least make some backtracking based on the edges it already visited. My main goal is to solve the euler path problem.

Code :

```public class Graph {   private int numVertex; private int numEdges; private boolean[][] adj;   public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex+1][numVertex+1]; }   public void addEdge(int start, int end){ adj[start][end] = true; adj[end][start] = true; }   List<Integer> visited = new ArrayList<Integer>();   public Integer DFS(Graph G, int startVertex){ int i=0; pilha.push(startVertex); boolean hasAdjacent = false; for(i=0; i<G.numVertex; i++){   if(G.adj[i][startVertex] != false){ hasAdjacent = true; System.out.println("i: " + i); G.adj[i][startVertex] = false; G.adj[startVertex][i] = false;   DFS(G, i); pilha.push(i);   G.adj[i][startVertex] = true; G.adj[startVertex][i] = true; }   /* else{ pilha.pop(); }*/   if(!pilha.isEmpty()){ int c = pilha.pop();   visited.add(c); System.out.println("visited: " + visited); }   } return -1; }   Stack<Integer> pilha = new Stack();   public static void main(String[] args) {   Graph g = new Graph(6, 9);   g.addEdge(1, 2); g.addEdge(1, 5); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(6, 4);   g.DFS(g, 1); } }```
• March 22nd, 2012, 12:09 PM
Norm
Re: Euler Paths with dfs algorithm problem
Quote:

Originally Posted by claudio.r
Here os the code with the main loading a graph. Currently it only makes a DFS search, i want to modify it to at least make some backtracking based on the edges it already visited. My main goal is to solve the euler path problem.

Code :

```public class Graph {   private int numVertex; private int numEdges; private boolean[][] adj;   public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex+1][numVertex+1]; }   public void addEdge(int start, int end){ adj[start][end] = true; adj[end][start] = true; }   List<Integer> visited = new ArrayList<Integer>();   public Integer DFS(Graph G, int startVertex){ int i=0; pilha.push(startVertex); boolean hasAdjacent = false; for(i=0; i<G.numVertex; i++){   if(G.adj[i][startVertex] != false){ hasAdjacent = true; System.out.println("i: " + i); G.adj[i][startVertex] = false; G.adj[startVertex][i] = false;   DFS(G, i); pilha.push(i);   G.adj[i][startVertex] = true; G.adj[startVertex][i] = true; }   /* else{ pilha.pop(); }*/   if(!pilha.isEmpty()){ int c = pilha.pop();   visited.add(c); System.out.println("visited: " + visited); }   } return -1; }   Stack<Integer> pilha = new Stack();   public static void main(String[] args) {   Graph g = new Graph(6, 9);   g.addEdge(1, 2); g.addEdge(1, 5); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(6, 4);   g.DFS(g, 1); } }```

What does the program do now? Can you post its output and explain what is wrong with the output and show what the output should be?
• March 22nd, 2012, 12:19 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
Right now, the program outputs the result of a dfs search on the graph:

Code :

```visited: [1] i: 2 visited: [1, 2] i: 4 visited: [1, 2, 4] i: 3 visited: [1, 2, 4, 3] i: 5 visited: [1, 2, 4, 3, 5] i: 1 visited: [1, 2, 4, 3, 5, 1] visited: [1, 2, 4, 3, 5, 1, 1] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2] i: 3 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3] i: 5 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5] i: 2 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2] i: 1 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1] i: 4 visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3, 4] visited: [1, 2, 4, 3, 5, 1, 1, 2, 2, 4, 4, 5, 3, 5, 1, 1, 2, 2, 3, 4, 4, 3, 5, 4, 5, 1, 1, 3, 4, 2, 2, 5, 1, 1, 5, 4, 3, 4, 2, 2, 3, 5, 1, 1, 5, 3, 4, 5, 2, 5, 2, 1, 1, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 4, 3, 5, 4, 2, 3, 4, 2, 1, 1, 5, 4, 4, 5, 2, 5, 2, 1, 1, 4, 4, 2, 5, 4, 3, 4, 2, 1, 1, 5, 3, 4, 4, 3, 5, 2, 3, 5, 2, 1, 1, 4, 4, 2, 5, 3, 4, 5]```

What i want is to have an euler path, where the program visits each one of the graph edges only once. So, in this particular example the correct output should be all the euler path on the graph such as:

Code :

`1 2 4 3 5 2 6 4 5 1`

To achieve this i think the first step should be, add backtracking to my DFS search, but i'm having trouble with that.
• March 22nd, 2012, 12:21 PM
Norm
Re: Euler Paths with dfs algorithm problem
Is this an algorithm question
or do you have the algorithm and want help coding it in java?
I might be able to help with the second one.
• March 22nd, 2012, 12:28 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
I have the algorithm, i need helping with the java part.

This is what i'm trying to achieve:
Euler tour - Algorithmist

right now i have an adjacency matrix, that is populated with the all the graph adjacencys. I'm performing DFS search on the graph, it runs through the graph choosing the first edge it finds in the adjacency list.
What i wnat right now, is to limit the edges he chooses, in a way that he only visits edges he has no visited before.
• March 22nd, 2012, 12:33 PM
Norm
Re: Euler Paths with dfs algorithm problem
Quote:

i need helping with the java part.
What are your java programming questions?
• March 22nd, 2012, 12:46 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
Right now, i'm trying to use a stack strucuture to remove a node from the list, but everytime i try to use pop() i get exceptions.

This is my current code:

Code :

```public class Graph {   private int numVertex; private int numEdges; private boolean[][] adj;   public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex+1][numVertex+1]; }   public void addEdge(int start, int end){ adj[start][end] = true; adj[end][start] = true; }   List<Integer> visited = new ArrayList<Integer>();   public Integer DFS(Graph G, int startVertex){ int i=0; pilha.push(startVertex); boolean hasAdjacent = false; for(i=0; i<G.numVertex; i++){   if(G.adj[i][startVertex] != false){ hasAdjacent = true; System.out.println("i: " + i); G.adj[i][startVertex] = false; G.adj[startVertex][i] = false;   pilha.push(i); DFS(G, i); }   else{ hasAdjacent=false; } }   //System.out.println("Conteudo da pilha: " + pilha);   if(!hasAdjacent){ pilha.pop(); DFS(G, pilha.firstElement());   } return -1; }   Stack<Integer> pilha = new Stack();   public static void main(String[] args) {   Graph g = new Graph(6, 9);   g.addEdge(1, 2); g.addEdge(1, 5); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(6, 4);   g.DFS(g, 1);   } }```
• March 22nd, 2012, 12:51 PM
Norm
Re: Euler Paths with dfs algorithm problem
Can you post the full text of the error message.
One reason you get an exception is if the stack is empty.
• March 22nd, 2012, 12:58 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
Here's the full error message:

Code :

```java.lang.StackOverflowError at java.util.Vector.ensureCapacityHelper(Unknown Source) at java.util.Vector.addElement(Unknown Source) at java.util.Stack.push(Unknown Source) at Graph.DFS(Graph.java:28) at Graph.DFS(Graph.java:65) at Graph.DFS(Graph.java:65) at Graph.DFS(Graph.java:65)```

I had errors because of empty stack too. I'm having trouble with the stack operations.

If you read python, what i'm trying to do is something like this: Finding Eulerian path in undirected graph Python recipes ActiveState Code

Only with diferent syntax and inputs.
• March 22nd, 2012, 01:02 PM
Norm
Re: Euler Paths with dfs algorithm problem
Looks like an infinite loop.

Try debugging by adding some printlns to show the values that are being used to see why it is not stopping.
• March 22nd, 2012, 03:12 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
Right now i can find the simple euler paths. But when the algorithm needs to backtrack i have a problem.

this is my current code:

Code :

```public class Graph {   private int numVertex; private int numEdges; private boolean[][] adj;   public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex][numVertex]; }   public void addEdge(int start, int end){ adj[start-1][end-1] = true; adj[end-1][start-1] = true; }   List<Integer> visited = new ArrayList<Integer>();   public Integer DFS(Graph G, int startVertex){ int i=0;   if(pilha.isEmpty()) pilha.push(startVertex);   for(i=1; i<G.numVertex; i++){ pilha.push(i); if(G.adj[i-1][startVertex-1] != false){ G.adj[i-1][startVertex-1] = false; G.adj[startVertex-1][i-1] = false; DFS(G,i); break; }else{ visited.add(pilha.pop()); } System.out.println("Stack: " + pilha); } return -1; }   Stack<Integer> pilha = new Stack();   public static void main(String[] args) {   Graph g = new Graph(6, 9);   g.addEdge(1, 2); g.addEdge(1, 5); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(6, 4);   g.DFS(g, 1);   } }```

If you execute the code, it stops in 1, when in reality, it should backtrack to 5 and select the edge to 2. Any ideia on how to solve this problem? I think the issue is in the stack operations... but i really don't know.
• March 22nd, 2012, 03:25 PM
Norm
Re: Euler Paths with dfs algorithm problem
Read the code's comments does not tell me anything about what the code is trying to do.
Where does it "stop" or "backtrack"?
"stops in 1" and "backtrack to 5" have no meaning
• March 22nd, 2012, 04:19 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
The code output should be 1 2 4 3 5 2 6 4 5 1 that represent the order in the graph that the nodes are visited. The out put of the program is 1 2 4 3 5 1 2 6 4 5, which means that he is visiting an edge it already visited "1 2". What i wanted to happen is that when it finds out that he is going to an edge he already visited, the program backtracks to the node after, and visit a different edge instead.
• March 22nd, 2012, 04:24 PM
Norm
Re: Euler Paths with dfs algorithm problem
Where in the code does it detect that it has visited an edge?
Where does the code backtrack to a node?
• March 22nd, 2012, 04:34 PM
claudio.r
Re: Euler Paths with dfs algorithm problem
It is supposed to backtrack in the pop() instruction, and after we visit an edge, i delete that edge from the matrix. The problem, is that when the program goes to a dead end, it does not backtrack, which means i'm doing something wrong in the code...
• March 22nd, 2012, 04:39 PM
Norm
Re: Euler Paths with dfs algorithm problem
The only way I know to find logic problems is to debug the code while it is running. If you don't have an interactive debugger, use lots of println statements to show variables' values and execution flow.