Searching in depth using a stack

Question

I’m trying to do an in-depth search using a stack, but it’s making a mistake on a if and I don’t know why.

   package Grafos;
import java.io.*;
import java.util.*;
public class Grafo {
    LinkedList<Integer> Arestas [];
    int n;
    int qtd_Arestas = 0;
    public Grafo(int n){
        this.n = n;
        Arestas = new LinkedList[n];
        for (int i=0; i<n; ++i)
            Arestas[i] = new LinkedList();
    }
    public void Adiciona_aresta(int origem, int destino){
        Arestas[origem].add(destino);
        qtd_Arestas++;
    }
    public int DFS(int S, boolean visited[], int contador){
        visited[S] = true;
        ListIterator<Integer> v = Arestas[S].listIterator();
        while(v.hasNext()) {
            n = v.next();
            System.out.println(S + ">>" + n);
            if(!visited[n]){
                contador = DFS(n,visited,contador+1);
            }
        }
        return contador+1;

    }
    public void DFS_ini(int S){
        boolean Visitados[] = new boolean [n];
        int contador = 0;
        int b = DFS(S,Visitados,contador);
        System.out.println("____________________________________________________");
    }

    public void Pilha_DFS(int S) {
        boolean visitados [] = new boolean [n];
        for(int i = 0; i < n;i++){
            visitados[i] = false;
        }
        int gatilho;
        int topo;
        visitados[S] = true;
        Stack pilha = new Stack();
        pilha.push(S);
        while(!pilha.isEmpty()){
            topo = (int) pilha.firstElement();
            if(Arestas[S].isEmpty()){
                gatilho = 1;
                break;
            }
            for(int linha : Arestas[S]) {
                if(visitados[linha] == false){//Erro aqui
                    System.out.println(S + ">>" + linha);
                    visitados[linha] = true;
                    pilha.add(linha);
                    S = linha;
                }else if(visitados[topo] == true){
                    pilha.remove(topo);
                }
            }
        }

    }
}

Error presented:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
    at Grafos.Grafo.Pilha_DFS(Grafo.java:55)
    at Grafos.Main.main(Main.java:12)

Answer 1

The procedure should be more or less like this:

1. Inserts the first node into the stack and marks as visited.

2. While there are nodes in the stack, pop the knot and stack all your neighbors that have not been visited, marking them as visited.

Note that there is a restriction there: Only visited nodes can enter the stack. This means that the else if in the end is a violation of that restriction. More than that, it’s a violation of the concept of a stack, where you’re trying to remove an element from the middle of the stack rather than from the top. That remove shouldn’t be there.

The class java.util.Stack inherits the method remove(int) of java.util.Vector. This method does not do what you expect it would do. It will not remove the element topo of the pile. Instead, it will interpret topo as being the position of the element to be removed. This will totally mess with your stack.

Even, it is not recommended to use the class java.util.Stack due to numerous design failures that she has (mainly by inheriting from Vector). See more about this here. Ideally you implement your own stack (I’ll give a different name to avoid confusion):

import java.util.NoSuchElementException;

public interface Pilha<T> {
    public T top() throws NoSuchElementException;
    public T pop() throws NoSuchElementException;
    public void push(T element);
    public boolean isEmpty();
}

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class PilhaArrayList<T> implements Pilha<T> {
    private final List<T> elementos;

    public PilhaArrayList() {
        this.elementos = new ArrayList<>();
    }

    @Override
    public T top() throws NoSuchElementException {
         if (isEmpty()) throw new NoSuchElementException();
         return elementos.get(elementos.size() - 1);
    }

    @Override
    public T pop() throws NoSuchElementException {
         if (isEmpty()) throw new NoSuchElementException();
         return elementos.remove(elementos.size() - 1);
    }

    @Override
    public void push(T element) {
        elementos.add(element);
    }

    @Override
    public boolean isEmpty() {
        return elementos.isEmpty();
    }
}

Your tidy code should be like this:

    public void pilhaDFS(int s) {
        boolean[] visitados = new boolean[n];
        visitados[s] = true;
        Pilha<Integer> pilha = new PilhaArrayList<>();
        pilha.push(s);
        while (!pilha.isEmpty()) {
            int topo = pilha.pop();
            for (int linha : arestas[s]) {
                if (visitados[linha]) continue;
                System.out.println(s + ">>" + linha);
                visitados[linha] = true;
                pilha.push(linha);
            }
        }
    }

Note that the value of the variable gatilho was never read anywhere, and therefore was useless. The break that accompanied the gatilho was harmful because it prevented his search to go back a few steps and try to continue down another path as soon as he found the first "dead end". Initialize the array visitados with all false is unnecessary because every array of boolean is already created with false in all positions.

Finally, it’s a good idea to follow the code conventions as regards the nomenclature of variables.

Looking at the rest of the code, generic types and arrays do not go well together. I suggest modeling the edges with adjacency list:

private final Map<Integer, List<Integer>> arestas;

The code of your class looks like this:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public Grafo {
    private final Map<Integer, List<Integer>> arestas;
    private final int n;
    private int qtdArestas = 0;

    public Grafo(int n) {
        this.n = n;
        arestas = new HashMap<>();
    }

    public void adicionaAresta(int origem, int destino) {
        List<Integer> adjacencias = arestas.get(origem);
        if (adjacencias == null) {
            adjacencias = new ArrayList<>();
            arestas.put(origem, adjacencias);
        }
        adjacencias.add(destino);
        qtdArestas++;
    }

    // Resto da classe.
}

The method pilhaDFS that I showed above would look almost the same. The only change is that arestas[s] viraria arestas.get(s).

Your methods dfs would look like this:

    private int dfs(int s, boolean[] visited, int contador) {
        if (visited[s]) return contador;
        contador++;
        visited[s] = true;
        for (int n : arestas.get(s)) {
            System.out.println(s + ">>" + n);
            contador = dfs(n, visited, contador);
        }
        return contador;
    }

    public void dfs(int s) {
        int b = dfs(s, new boolean[n], 0);
        System.out.println(contador);
    }

Note that the dfs with various parameters is private.