java - 使用以下算法在 Java 中实现 BFS
问题描述
我是 Java 新手。任何人都可以请在下面的照片中给出“使用以下算法在 Java 中实现 BFS”吗?
要实现的代码:
import java.util.Scanner;
public class BFS{
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
int[][] graph = takeInputGraph(sc);
System.out.println("Give input of the source node");
int s = sc.nextInt();
bfs(graph,s);
}
public static int[][] takeInputGraph(Scanner sc){
System.out.println("Input the number of nodes in the graph");
int node = sc.nextInt();
System.out.println("Input the number of edges in the graph");
int edge = sc.nextInt();
int[][] mat = new int[node][node];
for(int c=0; c<edge; c++){
System.out.println("Enter the first node of the "+(c+1)+"th edge");
int node1 = sc.nextInt();
System.out.println("Enter the second node of the "+(c+1)+"th edge");
int node2 = sc.nextInt();
mat[node1][node2] = 1;
mat[node2][node1] = 1;
}
return mat;
}
public static void bfs(int[][] g, int s){
}
}
解决方案
public static void bfs(int[][] g, int s){
int[] d = new int[g.length], // distances
p = new int[g.length]; // previous node
Arrays.fill(d, Integer.MAX_VALUE); // set all distances to infinity
Arrays.fill(p, -1);
d[s] = 0; // distance to starting node is 0
Queue<Integer> q = new LinkedList<>();
q.add(s);
while(!q.isEmpty()){
int u = q.poll();
for(int v = 0; v < g.length; v++){
if(g[u][v] == 1 // edge exists
&& d[u] + 1 < d[v]){ // distance is less
d[v] = d[u] + 1;
p[v] = u;
q.add(v);
}
}
}
}
推荐阅读
- javascript - vue js html中如何根据json数据动态添加输入字段?
- css - 在主题包装代码(SASS)中使用&符号
- python - Django:夹层前端搜索模块
- opencv - Aruco 期望什么图像编码?
- facebook - Sammyk/LaravelFacebookSdk - 从不返回用户个人资料图片。总是返回这个网址:“https://lookaside.facebook.com/etc”
- angular - Angular4 - 取消选中复选框
- android - 系统杀死应用程序后 UI 无法正常工作
- entity-framework - System.InvalidOperationException:关系特定的方法只能在上下文使用关系数据库提供程序时使用
- c# - 将 sbyte[] 转换为 bool[] 并将 char[] 转换为 short[]
- android - 如何映射从 ImageReader Camera2 接收的图像的 CameraResult 的 getFrameNumber