Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Euler Paths with dfs algorithm problem

1. ## 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:

```public class Graph {

private int numVertex;
private int numEdges;

public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
}

public void addEdge(int start, int end){
}

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++){

System.out.println("i: " + i);

int c = pilha.pop();

System.out.println("visited: " + visited);

DFS(G, i);

}

}
return -1;
}

Stack<Integer> pilha = new Stack();

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

int numVertices = input.nextInt();
int startNode = input.nextInt();

Graph g = new Graph(numVertices, numLinks);

for(int i = 0; i<numLinks; i++){
}

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?

2. ## Re: Euler Paths with dfs algorithm problem

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?

3. ## 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.

4. ## 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.

```public class Graph {

private int numVertex;
private int numEdges;

public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
}

public void addEdge(int start, int end){
}

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++){

System.out.println("i: " + i);

DFS(G, i);
pilha.push(i);

}

/*			else{
pilha.pop();
}*/

if(!pilha.isEmpty()){
int c = pilha.pop();

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.DFS(g, 1);
}
}```

5. ## Re: Euler Paths with dfs algorithm problem

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.

```public class Graph {

private int numVertex;
private int numEdges;

public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
}

public void addEdge(int start, int end){
}

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++){

System.out.println("i: " + i);

DFS(G, i);
pilha.push(i);

}

/*			else{
pilha.pop();
}*/

if(!pilha.isEmpty()){
int c = pilha.pop();

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.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?

6. ## Re: Euler Paths with dfs algorithm problem

Right now, the program outputs the result of a dfs search on the graph:

```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:

`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.

7. ## 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.

8. ## 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.

9. ## Re: Euler Paths with dfs algorithm problem

i need helping with the java part.
What are your java programming questions?

10. ## 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:

```public class Graph {

private int numVertex;
private int numEdges;

public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
}

public void addEdge(int start, int end){
}

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++){

System.out.println("i: " + i);

pilha.push(i);
DFS(G, i);
}

else{
}
}

//System.out.println("Conteudo da pilha: " + pilha);

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.DFS(g, 1);

}
}```

11. ## 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.

12. ## Re: Euler Paths with dfs algorithm problem

Here's the full error message:

```java.lang.StackOverflowError
at java.util.Vector.ensureCapacityHelper(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.

13. ## 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.

14. ## 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:

```public class Graph {

private int numVertex;
private int numEdges;

public Graph(int numVertex, int numEdges) {
this.numVertex = numVertex;
this.numEdges = numEdges;
}

public void addEdge(int start, int end){
}

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);
DFS(G,i);
break;
}else{
}
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.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.

15. ## 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

16. ## 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.

17. ## 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?

18. ## 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...

19. ## 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.