Doubt in the implementation of the deep search in Graphs

Question

Doubt in the implementation of the deep search in Graphs

Navigation

#1 by (4 votes)

3

I am studying for an algorithm test and I ended up finding some problems implementing the DFS ( Depht-First Search / depth search) > 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 am trying to perform the search is this:

Iamusingasastructurealistoflistsfortheconstructionofthegraph.Theimpressionoftheedgesisasfollows:

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]

Theproblemis:apparentlythestackisonlyabletoreach/reachtheEvertex.InitiallyIthoughtthatthereferencesofthearcscouldbewrong,buttheverticesarecorrectlyconnectedtoeachother.Theoutput,whenIprintonthescreenthestackisasfollows:

[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]

ThefunnythingisthatwhenIremovethepilha.pop();aftertheloop,thecontentsofthestackistheresultofthelongestpath,butthecodegoesintoloop:

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

Nodeclassimplementation:

privatestaticclassNode{Stringvalor;ArrayList<Node>adjacencias;booleanvisitado;intmaiorSeq;NoderefMaxNextNode;charcolor;intdist;Nodepai;Node(Stringvalor){this.valor=valor;adjacencias=newArrayList<>();visitado=false;maiorSeq=0;refMaxNextNode=null;dist=0;}voidsetValor(Stringvalor){this.valor=valor;}booleanaddCaminho(NodeoutroNode){if(adjacencias.contains(outroNode)){returnfalse;}adjacencias.add(outroNode);returntrue;}voidsetVisitado(){this.visitado=true;}publicStringtoString(){return"" + valor;
    }

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

java grafo

asked by anonymous 28.06.2015 / 05:16

1 answer

Get the key pressed with minimized or unfocused application C # submitting submit button even when canceling

score 4 · Answer 1

The problem is where the pilha.pop() statement is located. 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 notice D is a node adjacent to A but not on the stack.

I'll show you why. It assumes that A is the source node . At the beginning of your algorithm you put this node in the stack and marks it as visited:

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

Then you search for any nodes adjacent to A that have not yet been visited. As it is the first iteration B, C and D have never been visited. After running 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 stack 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 pilha.pop() statement.

As your stack becomes [A, B, C] and you've just lost node D.

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 program execution (depends on the order in which you visit 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 see all vertices have been visited and B and C, which were the first nodes to be placed on the stack, are the last to be processed