题目地址：

https://leetcode.com/problems/bus-routes/

给定一个二维数组，每一行是一个公交车路线的每一个车站的编号。再给定两个车站的编号$S$和$T$，问从$S$到$T$至少坐多少个不同的公交车。

思路是BFS。先开一个哈希表$m_1$，存储每个车站所在的公交路线的下标，这样就可以通过这个哈希表找到某个车站能到达哪些车站。这样存储的好处是非常的省空间。否则如果直接存一个车站能到达哪些别的车站，空间占用会非常大。接着就是普通的BFS了。先开一个哈希表$m_2$记录哪些路线已经被访问过。将起点入队，然后通过$m_1$找到乘这辆车能到达哪些路线，如果某个路线的车之前已经被乘过了，就略过；否则标记这条路线为已经访问过，并遍历这条路线上的所有车站，如果找到了终点就返回答案，否则将这个车站入队。代码如下：

import java.util.*; public class Solution { public int numBusesToDestination(int[][] routes, int S, int T) { if (routes == null || routes.length == 0) { return -1; } // 如果出发点就等于终点，那么不需要乘车，返回0 if (S == T) { return 0; } // key是车站编号，value是其能够到达的路线在routes数组中的下标 Map<Integer, List<Integer>> mapToRouteIdx = new HashMap<>(); for (int i = 0; i < routes.length; i++) { for (int stop : routes[i]) { mapToRouteIdx.computeIfAbsent(stop, k -> new ArrayList<>()).add(i); } } // 开一个队列存储车站编号 Queue<Integer> queue = new LinkedList<>(); queue.offer(S); // 开一个哈希表存储已经访问过的路线在routes中的下标 Set<Integer> visited = new HashSet<>(); // 记录乘过的路线的个数 int res = 0; while (!queue.isEmpty()) { res++; // 要分层，所以先记录队列的size int size = queue.size(); for (int i = 0; i < size; i++) { // 取出当前车站，并遍历其能到达的路线 int cur = queue.poll(); for (int nextRouteIdx : mapToRouteIdx.get(cur)) { // 如果这条路线访问过，就说明这个路线上车站都遍历过了，直接跳过不必重复遍历 if (visited.contains(nextRouteIdx)) { continue; } // 否则将其标记一下 visited.add(nextRouteIdx); // 遍历这条路线上的所有车站 for (int nextStop : routes[nextRouteIdx]) { // 如果到达了终点，就返回步数 if (nextStop == T) { return res; } queue.offer(nextStop); } } } } return -1; } }

时空复杂度$O(n)$，$n$为车站个数。