3

Estou estudando para uma prova de algoritmos e acabei encontrando alguns problemas para implementar o DFS(Depht-First Search/busca em profundidade) utilizando a estrutura de dados Pilha.

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();
    }
}

O grafo que estou tentando realizar a busca é este:

inserir a descrição da imagem aqui

Estou utilizando como estrutura uma lista de listas para a construção do grafo. A impressão das arestas é a seguinte:

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]

O problema é: aparentemente a pilha só está conseguindo ir/alcançar o vértice E. Inicialmente achei que as referências dos arcos pudessem estar erradas, porém os vértices estão corretamente ligados entre si. A saída, de quando eu imprimo na tela a pilha é a seguinte:

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

O engraçado é que, quando eu removo o pilha.pop(); após o laço, o conteúdo da pilha é o resultado do maior caminho, porém o código entra em loop:

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

Implementação da classe Node:

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);
    }        
}
2
  • Podes colocar a definição da classe Node?
    – bruno
    Commented 28/06/2015 às 18:44
  • Implementação adicionada :) Commented 28/06/2015 às 19:22

1 Resposta 1

4

O problema está na local onde se encontra a instrução pilha.pop(). Este output deveria dar-te uma indicação de onde se encontra o problema:

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

Se reparares o D é um nó adjacente ao A mas não está na pilha.

Vou mostrar porquê. Assume que o A é o nó origem. No início do teu algoritmo colocas este nó na pilha e marcas como visitado:

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

Depois procuras todos os nós adjacentes ao A que ainda não foram visitados. Como é a primeira iteração B, C e D nunca foram visitados. Após a execução do ciclo

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();
    }                
}

A tua pilha contém [A, B, C, D].

O problema vem agora. Imediatamente após colocares o último nó adjacente ao A (neste exemplo o D), removes esse nó da pilha com a instrução pilha.pop().

Sendo que a tua pilha passa a [A, B, C] e acabaste de perder o nó D.

Podes solucionar esse problema alterando o local onde removes o elemento do topo da stack, por exemplo:

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:

Este será o conteudo da pilha durante a execução do programa (depende da ordem pela qual visitas os nós)

[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

Como podes verificar todos os vertices foram visitados e o B e o C, que foram os primeiros nós a ser colocados na pilha, são os últimos a ser processados

3
  • Então, eu havia pensado em colocar o pilha.pop() substituindo o pilha.peek(), porém assim eu não perco a ideia básica do DFS? De "mergulhar" no grafo, até não haver mais vértices não-descobertos e ir realizando o backtracking? O resultado, fazendo as substituições: [ ] [B, D] [B, D, F] [B, D, F] [B, D, F, I] [B, D, F, I] [B, D, F, I] [B, D, F] [B, D] [B] [ ] Commented 28/06/2015 às 23:26
  • Não é mesmo isso, não penso que percas a ideia básica do DFS. Tu vais carregando os novos nós na pilha e apenas quando tiveres visitado todos os não-visitados fazes backtrack. Se quiseres eu posso actualizar a resposta com um exemplo.
    – bruno
    Commented 29/06/2015 às 12:22
  • Claro, seria interessante. Commented 29/06/2015 às 14:53

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .