bfs最短路径算法 java

以下是使用BFS算法求解最短路径的Java代码实现：

import java.util.*;

public class BFSShortestPath {
    
    /**
     * 计算无向图中从起点到终点的最短路径
     * @param graph 无向图
     * @param start 起点
     * @param end 终点
     * @return 最短路径
     */
    public static List<Integer> shortestPath(List<List<Integer>> graph, int start, int end) {
        // visited用于标记某个节点是否被访问过
        boolean[] visited = new boolean[graph.size()];
        // queue用于辅助实现BFS算法
        Queue<List<Integer>> queue = new LinkedList<>();
        // 将起点加入队列
        queue.offer(Arrays.asList(start));
        // 标记起点已访问
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            List<Integer> path = queue.poll();
            int lastNode = path.get(path.size() - 1);
            if (lastNode == end) {
                return path;
            }
            for (int neighbor : graph.get(lastNode)) {
                if (!visited[neighbor]) {
                    List<Integer> newPath = new ArrayList<>(path);
                    newPath.add(neighbor);
                    queue.offer(newPath);
                    visited[neighbor] = true;
                }
            }
        }
        return new ArrayList<>();
    }
    
    /**
     * 测试代码
     */
    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(Arrays.asList(1, 2)); // 0节点的邻居节点是1和2
        graph.add(Arrays.asList(0, 3));
        graph.add(Arrays.asList(0, 3));
        graph.add(Arrays.asList(1, 2, 4));
        graph.add(Arrays.asList(3));
        
        List<Integer> shortestPath = shortestPath(graph, 0, 4);
        System.out.println(shortestPath); // [0, 2, 3, 4]
    }
}

在这个示例代码中，我们定义了一个`BFSShortestPath`类，并提供了一个`shortestPath`方法，用于计算无向图中从起点到终点的最短路径。这个方法使用BFS算法实现，通过一个队列来辅助实现BFS算法，同时使用一个`visited`数组来标记某个节点是否被访问过。在计算最短路径时，我们使用了Java中的`List`类来表示路径，这使得我们可以方便地在路径的末尾添加新的节点。