如何针对整数数组路径问题实现BFS算法？求建图方法及替代方案

一、BFS的图构建思路 #

不用提前构建完整的图，而是在BFS过程中动态生成可访问节点，这样更节省空间、效率更高：

1. 预处理哈希表：遍历数组，用字典value_to_indices记录每个数值对应的所有索引位置，比如数组[3,5,2,2,5]，字典里5对应的列表就是[1,4]。
2. 标记访问状态：用布尔数组visited记录每个索引是否被处理过，避免重复入队。
3. BFS队列操作：
   • 队列存储(当前索引, 已移动次数)，初始把(0, 0)入队，同时标记索引0为已访问。
   • 每次从队列取出一个元素：
     • 如果当前索引是数组最后一个位置，直接返回当前移动次数。
     • 处理相邻移动：检查当前索引-1和当前索引+1是否在数组范围内且未被访问，满足条件则标记访问并将(新索引, 次数+1)入队。
     • 处理等值跳转：从哈希表中取出当前数值对应的所有索引，遍历这些索引，未被访问的标记后入队（次数+1）。处理完该数值的所有跳转后，建议从哈希表中删除这个数值的记录——因为所有等值位置都已加入队列，后续再遇到该数值时无需重复处理，能大幅减少冗余操作。

举示例1的运行过程：
输入数组[3,5,2,2,5]，初始队列[(0,0)]。

• 取出(0,0)：相邻索引1未访问，入队(1,1)；数值3仅在0出现，无跳转。
• 取出(1,1)：相邻索引0已访问、索引2未访问，入队(2,2)；数值5对应索引1和4，4未访问，入队(4,2)。
• 取出(4,2)：这是最后一个索引，直接返回2，符合示例输出。

二、替代解法 #

双向BFS #

当数组规模较大时，双向BFS比普通BFS效率更高，核心是同时从起点和终点两个方向搜索，直到两侧路径相遇：

1. 维护两个队列，分别从起点（索引0）和终点（索引n-1）出发。
2. 维护两个访问记录结构（字典或数组），分别记录从起点到各索引的步数、从终点到各索引的步数。
3. 每次选择节点数量较少的队列进行扩展（处理相邻移动和等值跳转，逻辑同普通BFS）。
4. 当某个索引被两个队列都访问到时，总移动次数就是该索引在两个方向的步数之和，直接返回这个总和。

不推荐的解法 #

Dijkstra算法虽然也能解决最短路径问题，但本题中所有移动的代价都是1，BFS本身就是最优的最短路径算法，用Dijkstra反而会增加不必要的复杂度，没必要使用。

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