BFS也就是广度优先搜索算法，是解决无权图最短路径问题的常用方案，它的核心思路是从起点开始逐层遍历相邻节点，第一次到达目标节点时的路径就是最短路径。在Java中实现该算法时，需要遵循正确的逻辑流程，同时避开容易出现的各类问题。
BFS实现最短路径的核心逻辑
BFS求解最短路径的核心依赖队列的先进先出特性，配合访问标记避免重复遍历，具体流程可以分为以下几个步骤：
- 初始化队列，将起点加入队列，同时标记起点为已访问
- 记录每个节点的前驱节点，方便后续回溯得到完整路径
- 循环从队列中取出节点，遍历其所有未访问的相邻节点，将相邻节点加入队列并标记访问，同时记录前驱关系
- 当遍历到目标节点时，停止搜索，通过前驱节点回溯得到最短路径
Java中正确的实现示例
下面以无向无权图的邻接表存储为例，给出完整的BFS最短路径实现代码：
import java.util.*;
public class BFSShortestPath {
// 邻接表存储图结构
private Map<Integer, List<Integer>> graph;
// 节点数量
private int nodeCount;
public BFSShortestPath(int nodeCount) {
this.nodeCount = nodeCount;
graph = new HashMap<>();
// 初始化邻接表
for (int i = 0; i < nodeCount; i++) {
graph.put(i, new ArrayList<>());
}
}
// 添加无向边
public void addEdge(int u, int v) {
graph.get(u).add(v);
graph.get(v).add(u);
}
// BFS求解最短路径，返回起点到终点的路径列表，无路径返回空列表
public List<Integer> bfsShortestPath(int start, int end) {
// 访问标记数组
boolean[] visited = new boolean[nodeCount];
// 前驱节点数组，记录每个节点的上一个节点
int[] prev = new int[nodeCount];
Arrays.fill(prev, -1);
// 使用队列存储待遍历节点
Queue<Integer> queue = new LinkedList<>();
// 初始化起点
visited[start] = true;
queue.offer(start);
// BFS遍历
while (!queue.isEmpty()) {
int current = queue.poll();
// 到达终点，停止搜索
if (current == end) {
break;
}
// 遍历当前节点的所有相邻节点
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
prev[neighbor] = current;
queue.offer(neighbor);
}
}
}
// 回溯得到路径
List<Integer> path = new ArrayList<>();
if (prev[end] == -1 && start != end) {
// 起点和终点不连通，无路径
return path;
}
// 从终点回溯到起点
for (int at = end; at != -1; at = prev[at]) {
path.add(at);
}
// 反转得到从起点到终点的路径
Collections.reverse(path);
return path;
}
public static void main(String[] args) {
BFSShortestPath bfsPath = new BFSShortestPath(6);
// 构建测试图
bfsPath.addEdge(0, 1);
bfsPath.addEdge(0, 2);
bfsPath.addEdge(1, 3);
bfsPath.addEdge(2, 3);
bfsPath.addEdge(3, 4);
bfsPath.addEdge(3, 5);
List<Integer> path = bfsPath.bfsShortestPath(0, 5);
if (path.isEmpty()) {
System.out.println("起点到终点无可达路径");
} else {
System.out.println("最短路径为：" + path);
}
}
}
实现过程中的常见陷阱
1. 未正确标记访问节点
很多开发者容易忘记在将节点加入队列时就标记访问，而是在从队列取出节点时才标记，这会导致同一个节点被多次加入队列，不仅增加不必要的遍历开销，还可能在有环的图中导致死循环。正确的做法是在节点入队时就将其标记为已访问。
2. 错误使用数据结构
部分开发者会使用栈来实现BFS，这其实变成了深度优先搜索，得到的路径不一定是短路径。必须使用队列来实现BFS的逐层遍历逻辑，因为队列的先进先出特性才能保证先访问距离起点更近的节点。
3. 处理带权图时误用BFS
BFS仅适用于无权图或者所有边权重相同的情况，如果图的边有权重且权重不同，BFS得到的第一条路径不一定是总权重最小的路径，此时应该使用Dijkstra等适合带权图的算法。如果错误在带权图上使用BFS求解最短路径，会得到错误结果。
4. 前驱节点记录错误
如果没有正确记录每个节点的前驱节点，或者前驱节点被后续遍历覆盖，回溯时就会得到不完整的路径或者错误的路径。需要确保每个节点只在第一次被访问时记录其前驱节点，后续重复访问时不再更新前驱关系。
5. 忽略起点和终点相同的情况
当起点和终点为同一个节点时，最短路径就是只包含该节点的单元素列表，如果没有特殊处理这种情况，代码可能会返回空列表或者错误的结果，需要在实现时提前判断这种边界场景。
总结
BFS算法求解最短路径的实现逻辑并不复杂，但需要严格遵循访问标记、队列使用、前驱记录等核心要点，同时避开上述常见陷阱。在实际开发中，需要根据图的特性选择合适的算法，无权图优先使用BFS，带权图则选择更适配的算法，才能保证结果的正确性。