java bfs输出最短路径

可以使用BFS算法来输出最短路径。以下是Java代码示例：

import java.util.*;

public class ShortestPathBFS {
    public static void main(String[] args) {
        int[][] graph = {{0, 1, 1, 0, 0},
                         {1, 0, 1, 1, 0},
                         {1, 1, 0, 1, 1},
                         {0, 1, 1, 0, 1},
                         {0, 0, 1, 1, 0}};
        int start = 0;
        int end = 4;
        List<Integer> shortestPath = bfsShortestPath(graph, start, end);
        System.out.println("Shortest path from " + start + " to " + end + ": " + shortestPath);
    }

    public static List<Integer> bfsShortestPath(int[][] graph, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        int[] parent = new int[graph.length];
        Arrays.fill(parent, -1);

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == end) {
                break;
            }
            for (int i = 0; i < graph.length; i++) {
                if (graph[current][i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                    parent[i] = current;
                }
            }
        }

        List<Integer> shortestPath = new ArrayList<>();
        int current = end;
        while (current != -1) {
            shortestPath.add(current);
            current = parent[current];
        }
        Collections.reverse(shortestPath);
        return shortestPath;
    }
}

该程序使用邻接矩阵表示图，从起点开始执行BFS算法，直到找到终点。在BFS过程中，记录每个节点的父节点，以便在找到终点后回溯路径。最后，将路径反转并返回。