如何在邻接矩阵的广度优先搜索中跟踪每个顶点的深度? (Java)
How can I track the depth of each vertex in a breadth first search of an adjacency matrix? (Java)
我试图在邻接矩阵的广度优先搜索期间跟踪和打印每个节点的深度。
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 文件中读取,并且在我的其他方法中工作正常。我可以简单,也可以不简单
欢迎任何意见,谢谢。
如果需要更多信息,请告诉我。
用 N 个整数创建数组 "depth",其中 N 是节点数,并将其传递给 BFS
在 BFS 中,假设您将顶点 "u" 出列,您会发现它的邻居,并且对于 "u" 的每个新发现的邻居 "v",您设置 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;
}
我试图在邻接矩阵的广度优先搜索期间跟踪和打印每个节点的深度。
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 文件中读取,并且在我的其他方法中工作正常。我可以简单,也可以不简单
欢迎任何意见,谢谢。
如果需要更多信息,请告诉我。
用 N 个整数创建数组 "depth",其中 N 是节点数,并将其传递给 BFS
在 BFS 中,假设您将顶点 "u" 出列,您会发现它的邻居,并且对于 "u" 的每个新发现的邻居 "v",您设置 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;
}