bfs最短路径算法 java

下面是BFS最短路径算法的Java实现，假设图的节点编号从0开始：

import java.util.*;

public class ShortestPathBFS {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  //节点个数
        int m = scanner.nextInt();  //边的个数
        int[][] edges = new int[m][2];  //存储边信息
        for (int i = 0; i < m; i++) {
            edges[i][0] = scanner.nextInt();
            edges[i][1] = scanner.nextInt();
        }
        int start = scanner.nextInt();  //起点
        int end = scanner.nextInt();    //终点
        int[] dist = shortestPathBFS(n, edges, start);  //计算最短路径
        System.out.println(dist[end]);  //输出最短路径长度
    }

    //BFS计算最短路径
    public static int[] shortestPathBFS(int n, int[][] edges, int start) {
        List<List<Integer>> graph = new ArrayList<>();  //邻接表存储图
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int[] dist = new int[n];  //记录起点到各节点的最短距离
        Arrays.fill(dist, -1);
        dist[start] = 0;

        Queue<Integer> queue = new LinkedList<>();  //BFS队列
        queue.offer(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int next : graph.get(curr)) {
                if (dist[next] == -1) {  //如果next节点没有被访问过
                    dist[next] = dist[curr] + 1;
                    queue.offer(next);
                }
            }
        }
        return dist;
    }
}

在这个例子中，我们先输入节点个数n、边的个数m、m条边的信息、起点start和终点end。然后调用shortestPathBFS函数计算从起点到各个节点的最短距离，并输出终点的最短距离。