Doubt in the implementation of the deep search in Graphs

Question

I’m studying for a proof of algorithms and I ended up finding some problems to implement the DFS(Depht-First Search/deep search) using data structure Stack.

static void emProfundidade(ArrayList<Node> grafo, Node origem) {
    Stack<Node> pilha = new Stack<>();
    for (int i = 0; i < grafo.size(); i++) {
        grafo.get(i).visitado = false;            
    }

    pilha.push(origem);
    origem.setVisitado();

    while (!pilha.isEmpty()) {
        Node v = pilha.peek();
        System.out.println(pilha);

        for(int i = 0; i <v.adjacencias.size(); i++){
            Node adj = v.adjacencias.get(i);
            if(adj.visitado == false){
                System.out.println(v + " >> "+adj);
                pilha.push(adj);
                adj.setVisitado();
            }                
        }
        pilha.pop();
    }
}

The graph I’m trying to search is this:

I am using as a structure a list of lists for the construction of the graph. The impression of the edges is as follows:

A >> [B, C, D]
B >> [A, E, C]
C >> [A, B, D, F, G]
D >> [A, C, G]
E >> [B, F, H]
F >> [C, E, I]
G >> [D, C, J]
H >> [E, I, L]
I >> [F, H, L]
J >> [G, I, L]
L >> [H, I, J]

The problem is: apparently the stack is only getting to/from the vertex E. Initially I thought that the references of the arcs could be wrong, but the vertices are correctly connected. The output, when I print on the screen the stack is as follows:

[A]
[A, B, C]
[A, B, C, F]
[A, B, C, F, E]
[A, B, C, F, E]
[A, B, C, F]
[A, B, C]
[A, B]
[A]

The funny thing is, when I remove the pilha.pop(); after the loop, the stack content is the result of the longest path, however the code enters loop:

[A, B, C, D, G, J, I, L, H, E, F].

Implementation of the Node class:

private static class Node {

    String valor;
    ArrayList<Node> adjacencias;
    boolean visitado;
    int maiorSeq;
    Node refMaxNextNode;
    char color;
    int dist;
    Node pai;

    Node(String valor) {
        this.valor = valor;
        adjacencias = new ArrayList<>();
        visitado = false;
        maiorSeq = 0;
        refMaxNextNode = null;
        dist = 0;
    }

    void setValor(String valor) {
        this.valor = valor;
    }

    boolean addCaminho(Node outroNode) {
        if (adjacencias.contains(outroNode)) {
            return false;
        }

        adjacencias.add(outroNode);
        return true;
    }

    void setVisitado() {
        this.visitado = true;
    }

    public String toString() {
        return "" + valor;
    }

    public void pai() {
        System.out.println("O pai de " + valor + " é: " + pai);
    }        
}

Answer 1

The problem is where the instruction is pilha.pop(). This output should give you an indication of where the problem is:

[A]
[A, B, C]
[A, B, C, F]
[A, B, C, F, E]
[A, B, C, F, E]
[A, B, C, F]
[A, B, C]
[A, B]
[A]

If you repair D is a node adjacent to A but not on the stack.

I’ll show you why. Assume A is the origin node. At the beginning of your algorithm you place this node on the stack and mark as visited:

pilha.push(origem);
origem.setVisitado();

Then you look for all nodes adjacent to A that have not yet been visited. As is the first iteration B, C and D have never been visited. After the execution of the cycle

for(int i = 0; i <v.adjacencias.size(); i++){
    Node adj = v.adjacencias.get(i);
    if(adj.visitado == false){
        System.out.println(v + " >> " + adj);
        pilha.push(adj);
        adj.setVisitado();
    }                
}

Your pile contains [A, B, C, D].

The problem comes now. Immediately after you place the last node adjacent to A (in this example D), you remove that node from the stack with the instruction pilha.pop().

Since your stack passes to [A, B, C] and you just lost the D-knot.

You can solve this problem by changing the location where you remove the element from the top of the stack, for example:

static void emProfundidade(ArrayList<Node> grafo, Node origem) {
    Stack<Node> pilha = new Stack<>();
    for (int i = 0; i < grafo.size(); i++) {
        grafo.get(i).visitado = false;            
    }

    pilha.push(origem);
    origem.setVisitado();

    while (!pilha.isEmpty()) {
        Node v = pilha.pop(); //substituir o peek pelo pop
        System.out.println(pilha);

        for(int i = 0; i <v.adjacencias.size(); i++){
            Node adj = v.adjacencias.get(i);
            if(adj.visitado == false){
                System.out.println(v + " >> "+adj);
                pilha.push(adj);
                adj.setVisitado();
            }                
        }
        //pilha.pop();  -- Remover daqui
    }
}

Edit:

This will be the content of the stack during the execution of the program (it depends on the order in which visits the nodes)

[A]              - No inicio do algoritmo colocamos o A na pilha
[B, C, D]        - Após o ciclo for, todos os nós adjacentes a A estão na pilha. Repara que o A foi removido da mesma
[B, C, G]        - Na próxima iteração vamos procurar os nós adjacentes ao último nó visitado, neste caso o D. Ele tem três nós adjacentes, mas como o A e o C já foram visitados apenas colocamos o G no topo da pilha. E é o G o próximo nó que processamos (DFS).
[B, C, J]        - Após processar o G que tem 3 nós adjacentes, mas uma vez mais dois deles já foram visitados, por isso só colocamos o J na pilha.
[B, C, I, L]     - Após processar o J
[B, C, I, H]     - Após processar o L
[B, C, I, E]     - Após processar o H
[B, C, I, F]     - Após processar o E
[B, C, I]        - Após processar o F, que é o primeiro nó que não tem adjacentes não visitados. Aqui começamos a fazer backtrack
[B, C]           - Após processar o I
[B]              - Após processar o C

As you can check all the vertices were visited and the B and C, which were the first nodes to be placed on the stack, are the last to be processed