如何在邻接矩阵的广度优先搜索中跟踪每个顶点的深度?

我试图在邻接矩阵的广度优先搜索期间跟踪并打印每个节点的深度。


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 文件中读取,并且在我的其他方法中运行良好。我可以是任意大小的简单,也可以不是。


任何意见表示赞赏,谢谢。


如果需要更多信息,请告诉我。


白猪掌柜的
浏览 90回答 1
1回答

阿晨1998

用 N 个整数创建数组“深度”,其中 N 是节点数并将其传递到 BFS在 BFS 中,假设您将顶点“u”出列,您会发现它的邻居,并且对于“u”的每个新发现的邻居“v”,你设置depth[v]=depth[u] + 1:if(matrix[x-1][i] == 1 && visited[i] == false){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue.add(i+1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; visited[i] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; depth[i] = depth[x]+1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp;
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java