公交路线——全量遍历的路线BFS

需要解决的问题是：给定多条公交路线（每条路线包含若干站点），以及起点和终点站点，求从起点到终点最少需要乘坐的公交线路数量（换乘次数 = 线路数 - 1）。

1.直接遍历站点会因站点数量庞大导致效率低下 2.需保证找到 “最少换乘” 的最优解，而非任意可行解。

代码采用广度优先搜索 而非站点级遍历，核心逻辑是：
将 “公交线路” 作为图的节点，“两条线路有公共站点” 作为节点间的边（可换乘）；
从包含起点的所有线路出发，逐层遍历可换乘的线路；
一旦遍历到包含终点的线路，立即返回当前乘坐的线路数（保证最少）；
全程记录路径，确保能追溯具体换乘顺序。

核心是把公交线路抽象为图的节点、线路间有公共站点抽象为可换乘的边，通过层序遍历保证找到最少换乘的最优解。代码首先初始化一个存储自定义QueueNode结构体的队列，结构体包含当前换乘路径（line_path）和已乘坐线路数（path_amount），同时用visited数组标记已入队的线路避免重复处理；接着将所有包含起点的线路作为 BFS 初始层入队，设置初始线路数为 1、路径仅含该线路。随后进入队列循环，每次取出队首节点，获取当前路径的最后一条线路，遍历所有未访问线路，通过has_common_stop判断是否可换乘，若可换乘则检查目标线路是否包含终点，若包含则拼接路径并返回当前线路数（即最少换乘对应的线路数）；若未包含终点且线路数未超过限制，则复制当前路径、添加新线路、更新线路数后将新节点入队并标记为已访问。若队列遍历结束仍未找到终点，则返回 - 1 表示无可行路线，整个过程利用 BFS 逐层扩展的特性，确保第一次找到终点时的线路数即为最少乘车数，对应最少换乘次数。

queue<QueueNode> q;
vector<bool> visited(routes.size(), false);
for (int r_idx : start_routes) {
QueueNode node;
node.line_path.clear();
node.line_path.push_back(r_idx);
node.path_amount = 1;
q.push(node);
visited[r_idx] = true;
}

queue<QueueNode> q;

visited(routes.size(), false); QueueNode node; node.line_path.clear(); node.line_path.push_back(r_idx);

node.path_amount = 1;

q.push(node); // 节点入队 visited[r_idx] = true;

}

int result = -1;

while (!q.empty()) {

QueueNode cur = q.front(); q.pop();

int last_route = cur.line_path.back();

for (int i = 0; i < routes.size(); i++) { if (visited[i]) continue;

if (has_common_stop(routes[last_route], routes[i])) {

if (is_stop_in_route(T, routes[i])) {

line_path.clear(); for (int idx : cur.line_path) { line_path.push_back(idx + 1); } line_path.push_back(i + 1); result = cur.path_amount; return result; }

if (cur.path_amount + 1 < MAX_PATH) { QueueNode next_node; next_node.line_path = cur.line_path;

next_node.line_path.push_back(i);

next_node.path_amount = cur.path_amount + 1;

visited[i] = true;

q.push(next_node);

}

}

}

} return result;

本文解析的公交路线最短换乘代码，核心是将 “线路” 抽象为图节点、“换乘” 抽象为边，通过 BFS 的层序特性保证 “最少换乘” 的最优解。该方案兼顾了 “最优性” 和 “实用性”：
最优性：BFS 天然保证第一次找到终点时的换乘次数最少；
实用性：线路级遍历避免了站点级遍历的高复杂度，适配实际公交场景的规模。