使用以下算法在 Java 中实现 BFS

Question

我是 Java 的新人。任何人都可以在下面的照片中“使用以下算法在 Java 中实现 BFS”吗？

Algorithm.jpg

实现代码：


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){
      
   }
}

Answer 1

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);
            }
        }
    }
}

使用以下算法在 Java 中实现 BFS

Implement BFS in Java with following algorithm

java

algorithm

breadth-first-search