1
I need to implement a system of visits, and the search in Width (graphs).
How to proceed? [EDIT] I would like to know the best way to make this algorithm work for Graph as well, because it is currently only working specifically for trees without direction. I would like someone to show me the most "correct" way to implement the one method for searching in width, and a method that demonstrates which nodes have been traversed.
I did it:
public class GrafoMatriz {
int[][] grafo;
int[] visitas;
int nVertices;
int[] profundidade;
public void getMatriz(String file) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line = "";
line = br.readLine();
nVertices = Integer.parseInt(line);
grafo = new int[nVertices][nVertices];
visitas = new int[nVertices];
line = br.readLine();
while (line != null) {
String[] pares = line.split(" ");
grafo[Integer.parseInt(pares[0])][Integer.parseInt(pares[1])] = 1;
// matriz[Integer.parseInt(pares[1])][Integer.parseInt(pares[0])] =
// 1;
line = br.readLine();
}
profundidade = new int[nVertices];
br.close();
// return matriz;
}
public void imprimeMatriz() {
for (int i = 0; i < nVertices; i++) {
for (int j = 0; j < nVertices; j++) {
System.out.print(grafo[i][j]);
}
System.out.println();
}
System.out.println("\n--------------------\n");
}
public void zeraMatriz() {
for (int i = 0; i < grafo.length; i++) {
for (int j = 0; j < grafo[i].length; j++) {
grafo[i][j] = 0;
}
}
}
public void geraListaVisitas(int no1, int no2) {
zeraLista();
eAlcancavel(no1, no2);
imprimeLista();
}
public void eAlcancavel(int no1, int no2) {
visitas[no1] = 1;
for (int i = 0; i < visitas.length; i++) {
if (grafo[no1][i] == 1) {
eAlcancavel(i, no2);
}
}
}
public void imprimeLista() {
for (int i = 0; i < visitas.length; i++) {
System.out.print(visitas[i] + " ");
}
}
public void zeraLista() {
for (int i = 0; i < visitas.length; i++) {
visitas[i] = 0;
}
}
public void profundidade(int x){
profundidade[x]++;
}
}
And what is your doubt?
– Jéf Bueno
Depth search uses direct stack/recursion. Width search does searches through a queue
– Jefferson Quesado
Sorry, I’ll edit the question.
– JoubertJoe .Vieira Lellis