Busca em profundidade em um grafo usando pilha

4 respostas
java
N

Eu estava tentando fazer uma busca em profundidade usando uma pilha, mas esta dando erro em um if meu e nao sei o pq. ai o codigo completo(o erro ta em Pilha_DFS).

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];
        visitados[s] = true;
        Pilha<Integer> pilha = new PilhaArrayList<>();
        pilha.push(s);
        while (!pilha.isEmpty()) {
            int topo = pilha.pop();
            for (int linha : Arestas[topo]) {
            	
            	try{
            		if (visitados[linha]) continue;
            	
	                System.out.println(topo + ">>" + linha);
	                visitados[linha] = true;
	                pilha.push(linha);
            	}catch(Exception e) {
            		e.printStackTrace();
            	}
	        }
        }
    }
}

4 Respostas

Crocodilo

Vou ser honesto, estou estudando o mesmo assunto, mas usando outra, linha de pensamento, vamos deixar alguém mais experiente questionar seu Grafo, mas só pela a estrutura apresentada me parece que você vai indo bem …

N

Cara, eu quero muito fazer amigos principalmente da aŕea, pois duas pessoas resolvem um problemas mais facil e resolvendo outros problemas eu também aprendo, espero estar indo certo mesmo.

staroski

Que erro?

D

Eu usaria uma estrutura diferente:

LinkedList<Point> arestas;

e para verificar os visitados:

HashSet<Point> visitados = new HashSet<>();
visitados.add(new Point(1,2));
System.out.println(visitados.contains(new Point(1, 2)));
System.out.println(visitados.contains(new Point(1, 3)));

ou

HashSet<Integer> visitados = new HashSet<>();
visitados.add(1);
System.out.println(visitados.contains(1);
System.out.println(visitados.contains(2);
Criado 31 de agosto de 2018
Ultima resposta 2 de set. de 2018
Respostas 4
Participantes 4