基于BFS算法实现两点间最短路径的代码技术咨询

嘿，我看你已经搭好了Graph类的基础框架，这正是实现BFS最短路径的绝佳起点！先把你给出的代码补全并整理清晰，再加上核心的最短路径求解逻辑：

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class Graph {
    private int V;
    private LinkedList<Integer> adj[]; // 邻接表存储结构

    // 构造函数：初始化顶点数和邻接表
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 向图中添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
        // 如果是无向图，记得加上这行，保证双向连通
        // adj[w].add(v);
    }

    // 核心方法：求解从start到end的最短路径
    public List<Integer> shortestPath(int start, int end) {
        // 记录每个节点的父节点，用于后续回溯路径
        int[] parent = new int[V];
        // 标记节点是否被访问过，避免重复遍历
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        // 初始化：所有节点父节点设为-1，未访问状态
        for (int i = 0; i < V; i++) {
            parent[i] = -1;
            visited[i] = false;
        }

        // 起点入队并标记为已访问
        visited[start] = true;
        queue.add(start);

        // BFS核心遍历逻辑
        while (!queue.isEmpty()) {
            int currentNode = queue.poll();

            // 找到目标节点，提前终止遍历
            if (currentNode == end)
                break;

            // 遍历当前节点的所有邻接节点
            for (int neighbor : adj[currentNode]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = currentNode;
                    queue.add(neighbor);
                }
            }
        }

        // 回溯构造最短路径
        List<Integer> path = new ArrayList<>();
        for (int i = end; i != -1; i = parent[i]) {
            path.add(i);
        }
        // 反转路径，得到从起点到终点的正序
        Collections.reverse(path);

        // 特殊情况处理：如果起点终点不重合但路径只有终点，说明两点无连通路径
        if (path.size() == 1 && start != end) {
            return new ArrayList<>();
        }

        return path;
    }
}

// 测试示例
public class BFSShortestPathDemo {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);

        List<Integer> resultPath = graph.shortestPath(0, 5);
        if (!resultPath.isEmpty()) {
            System.out.println("两点间最短路径: " + resultPath);
        } else {
            System.out.println("起点和终点之间不存在连通路径");
        }
    }
}

关键细节说明 #

• 邻接表设计：你的初始代码已经正确实现了邻接表的初始化，这是BFS高效遍历的基础，能快速获取每个节点的所有邻接点。
• BFS特性利用：BFS是按层级遍历节点的，第一次到达目标节点时的路径必然是最短路径，这也是我们选择它来求最短路径的核心原因。
• 路径回溯：通过父节点数组从终点反向追溯到起点，再反转得到正序路径，清晰直观地还原最短路径。
• 无向图适配：如果你的图是无向结构，只需在addEdge方法中添加反向边的注册即可，无需修改BFS核心逻辑。

测试输出 #

上面的示例代码会输出：两点间最短路径: [0, 1, 3, 4, 5]（或[0,2,3,4,5]，取决于BFS遍历邻接点的顺序，两条都是最短路径）。

内容的提问来源于stack exchange，提问作者Sveta Tulova