基于双向 BFS 的公交换乘最优路径规划系统设计与实现
在日常出行场景中，公交换乘路径规划是高频需求，核心诉求是最少换乘次数。传统单向广度优先搜索（BFS）在面对多线路、长距离场景时，存在搜索空间大、效率低的问题。本文将介绍一种基于双向 BFS的公交换乘最优路径规划方案，通过从起点和终点双向同步搜索，大幅缩减搜索空间，实现高效的路径规划，并附上完整可运行的 C++ 代码及详细解析。
一、核心算法原理
1. 双向 BFS vs 单向 BFS
单向 BFS 的搜索逻辑是从起点出发，逐层向外扩展直至找到终点，搜索空间呈指数级增长（复杂度为 O(bd)，b 为每层分支数，d 为搜索深度）。
双向 BFS 则同时从起点和终点两个方向开始层序搜索，当两个方向的搜索队列相遇时，即可终止搜索。其搜索空间复杂度为 O(2×bd/2)，相比单向 BFS，效率提升显著，尤其在长距离路径规划场景中优势明显。
2. 以 “线路” 为搜索节点的设计巧思
传统 BFS 以 “车站” 为搜索节点，但本系统的核心目标是最少换乘次数，换乘的本质是 “线路切换”。因此，我们将 BFS 的搜索节点定义为公交线路，这样 BFS 的 “层数” 就直接对应 “乘坐的线路数”，换乘次数 = 线路数 - 1。
该设计的优势在于：利用 BFS“层序遍历，先到先最优” 的特性，确保第一次相遇时找到的路径就是换乘次数最少的最优路径。
3. 核心数据结构：车站 - 线路映射表
为了快速通过车站找到可换乘的线路，我们构建了哈希映射表zhanTolu，其键为车站编号，值为该车站所属的线路索引列表。这个映射表是实现线路扩展的核心，能够快速关联不同线路，支撑双向 BFS 的高效搜索。
二、系统整体架构与功能模块
本系统采用模块化设计，分为输入处理模块、核心算法模块、结果输出模块三大模块，整体流程为：输入线路与起止站 → 双向BFS路径搜索 → 输出最优换乘方案。
1. 输入处理模块
负责读取用户输入的公交线路信息、起点和终点车站，并完成输入合法性校验，包括：
- 线路数量为正整数校验；
- 线路车站列表非空校验；
- 车站编号在合法范围（0~1000000）校验。
核心函数包括inputlu()（读取线路）、inputSE()（读取起止站）、qukong()（去除输入空格）、jiexi()（解析线路字符串）、check()（校验车站编号）。
2. 核心算法模块
这是系统的核心，通过findbus()函数实现双向 BFS 的完整逻辑，包括：
- 异常场景预处理（无线路、车站非法、起止站相同等）；
- 构建
zhanTolu车站 - 线路映射表； - 初始化正向 / 反向搜索队列、访问标记数组、层数计数数组；
- 交替扩展正向 / 反向队列，判断搜索相遇；
- 相遇后回溯路径，生成换乘方案。
辅助函数findzhan()用于查找两条线路的共同换乘站，支撑路径拼接。
3. 结果输出模块
通过show()函数，根据核心算法模块返回的状态码和路径信息，友好输出结果，包括：
- 正常场景：直达方案、换乘方案（含换乘步骤、线路数、换乘次数）；
- 异常场景：无有效线路、车站不存在、无可达路径等明确提示。
三、完整代码实现
四、关键代码解析
1. 双向 BFS 初始化
分别初始化正向队列q1（起点所在线路）和反向队列q2（终点所在线路），同时初始化访问标记数组v1/v2（记录线路是否被访问）、层数数组d1/d2（记录到该线路的乘坐线路数）、父节点数组p1/p2（用于路径回溯）。
特别地，在反向队列初始化时，会直接判断起点和终点是否在同一条线路，若存在则直接返回直达方案。
2. 交替扩展队列
双向 BFS 的核心是交替处理正向和反向队列的一层节点，确保层序遍历的特性。对于每一条当前线路，遍历其所有车站，通过zhanTolu映射表找到可换乘的线路：
- 若该线路未被当前方向访问过，则标记访问状态、更新层数和父节点，并加入队列；
- 若该线路已被对方方向访问过，则判定为搜索相遇，触发路径回溯逻辑。
3. 路径回溯与拼接
当搜索相遇时，分别从相遇线路回溯正向路径（起点→相遇线路）和反向路径（终点→相遇线路），拼接得到完整路径。再通过findzhan()函数查找相邻线路的换乘站，最终生成包含 “线路索引 + 换乘站” 的结果列表。
五、测试案例与运行结果
测试案例
输入线路数量：3
- 线路 1：1 2 3
- 线路 2：3 4 5
- 线路 3：5 6 7
- 起点：1 终点：7
运行结果
六、总结
本文设计的基于双向 BFS 的公交换乘路径规划系统，通过 “以线路为搜索节点” 的创新设计，高效实现了最少换乘次数的路径规划。系统具备完善的异常处理机制，能够友好响应用户输入，在日常出行、智能导航等场景中具有较高的实用价值。