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