Search Width and Depth in a graph

Asked

Viewed 495 times

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]++;
    }
}
  • 2

    And what is your doubt?

  • Depth search uses direct stack/recursion. Width search does searches through a queue

  • Sorry, I’ll edit the question.

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.