Как я могу отслеживать глубину каждой вершины в первом поиске матрицы смежности в ширину? (Ява) - PullRequest
Новая
       20

Как я могу отслеживать глубину каждой вершины в первом поиске матрицы смежности в ширину? (Ява)

0 голосов
/ 05 октября 2019

Я пытаюсь отследить и напечатать глубину каждого узла при первом поиске матрицы смежности в ширину. 

public class steptwo {
static String matrixFileName = "matrix.txt";

static int[][] matrix;
static int dimensions = 0;

public static void main(String[] args) {

    matrix = analyzeFile();
    bft();

}

static void bft(){

    Scanner input = new Scanner(System.in);
    System.out.println("Please enter the source vertex, 0 to " + (matrix.length-1) + ".");

    int source = input.nextInt()+1;


    //Testing for valid vertex 
    while (source > matrix.length) {
        System.out.println("Invalid vertex, please enter another from 0 to " + (matrix.length-1) + ".");
        source = input.nextInt()+1;
    }
    input.close();

    boolean[] visited = new boolean[matrix.length];

    visited[source - 1] = true;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(source);
    int height = 0;
    System.out.println("The breadth first order is: ");

    while(!queue.isEmpty()){
        System.out.print(queue.peek()-1 + " ---> H");
        int x = queue.poll();
        int i;

        for(i = 0 ; i < matrix.length; i++){
            if(matrix[x-1][i] == 1 && visited[i] == false){
                queue.add(i+1);
                visited[i] = true;
                height++;
            }

        }
        System.out.print(height + "\n");
    }
}

Я ищу вывод, отформатированный так: 

Please enter the source vertex, 0 to 7.
0
The breadth first order is: 
0 ---> H5
1 ---> H6
2 ---> H6
3 ---> H6
4 ---> H7
5 ---> H7
6 ---> H7
7 ---> H7

Я уверен, что мне просто не хватает чего-то глупого, но я в растерянности. Мне нужно отслеживать глубину каждой доступной вершины. Матрица смежности успешно читается из файла .txt и отлично работает в других моих методах. Я могу быть любого размера, простым или нет.

Любой вклад приветствуется, Спасибо.

Если вам нужна дополнительная информация, пожалуйста, дайте мне знать.

1 Ответ

1 голос
/ 05 октября 2019

Сделать массив "глубиной" с N целыми числами, где N - это число узлов, и передать его в BFS
В BFS, скажем, если вы удалили вершину из вершины "u", вы обнаружите ее соседей и для каждого вновь обнаруженного соседа "v"из" u, вы устанавливаете depth[v]=depth[u] + 1: 

if(matrix[x-1][i] == 1 && visited[i] == false){
                queue.add(i+1);
                visited[i] = true;
                depth[i] = depth[x]+1;
            }
...