网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 815. 公交路线 ，难度为 困难。
Tag : 「图论 BFS」、「双向 BFS」、「图论搜索」
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
- 例如，路线
routes[0] = [1, 5, 7]表示第 0 辆公交车会一直按序列1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2 解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 复制代码
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 输出：-1 复制代码
提示：
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 10^5105
- routes[i] 中的所有值 互不相同
- sum(routes[i].length) <= 10^5105
- 0 <= routes[i][j] < 10^6106
- 0 <= source, target < 10^6106
基本分析
为了方便，我们令每辆公交站为一个「车站」，由一个「车站」可以进入一条或多条「路线」。
问题为从「起点车站」到「终点车站」，所进入的最少路线为多少。
抽象每个「路线」为一个点，当不同「路线」之间存在「公共车站」则为其增加一条边权为 11 的无向边。
单向 BFS
由于是在边权为 11 的图上求最短路，我们直接使用 BFS 即可。
起始时将「起点车站」所能进入的「路线」进行入队，每次从队列中取出「路线」时，查看该路线是否包含「终点车站」：
- 包含「终点车站」：返回进入该线路所花费的距离
- 不包含「终点车站」：遍历该路线所包含的车站，将由这些车站所能进入的路线，进行入队
一些细节：由于是求最短路，同一路线重复入队是没有意义的，因此将新路线入队前需要先判断是否曾经入队。
网络异常，图片无法展示
|
代码：
class Solution { int s, t; int[][] rs; public int numBusesToDestination(int[][] _rs, int _s, int _t) { rs = _rs; s = _s; t = _t; if (s == t) return 0; int ans = bfs(); return ans; } int bfs() { // 记录某个车站可以进入的路线 Map<Integer, Set<Integer>> map = new HashMap<>(); // 队列存的是经过的路线 Deque<Integer> d = new ArrayDeque<>(); // 哈希表记录的进入该路线所使用的距离 Map<Integer, Integer> m = new HashMap<>(); int n = rs.length; for (int i = 0; i < n; i++) { for (int station : rs[i]) { // 将从起点可以进入的路线加入队列 if (station == s) { d.addLast(i); m.put(i, 1); } Set<Integer> set = map.getOrDefault(station, new HashSet<>()); set.add(i); map.put(station, set); } } while (!d.isEmpty()) { // 取出当前所在的路线，与进入该路线所花费的距离 int poll = d.pollFirst(); int step = m.get(poll); // 遍历该路线所包含的车站 for (int station : rs[poll]) { // 如果包含终点，返回进入该路线花费的距离即可 if (station == t) return step; // 将由该线路的车站发起的路线，加入队列 Set<Integer> lines = map.get(station); if (lines == null) continue; for (int nr : lines) { if (!m.containsKey(nr)) { m.put(nr, step + 1); d.add(nr); } } } } return -1; } } 复制代码
- 时间复杂度：令路线的数量为 nn，车站的数量为 mm。建图的时间复杂度为 O(\sum_{i=0}^{n-1} len(rs[i]))O(∑i=0n−1len(rs[i]))；
BFS部分每个路线只会入队一次，最坏情况下每个路线都包含所有车站，复杂度为 O(n * m)O(n∗m)。整体复杂度为 O(n * m + \sum_{i=0}^{n-1} len(rs[i]))O(n∗m+∑i=0n−1len(rs[i]))。 - 空间复杂度：O(n * m)O(n∗m)
双向 BFS（并查集预处理无解情况）
另外一个做法是使用双向 BFS。
首先建图方式不变，将「起点」和「终点」所能进入的路线分别放入两个方向的队列，如果「遇到公共的路线」或者「当前路线包含了目标位置」，说明找到了最短路径。
另外我们知道，双向 BFS 在无解的情况下不如单向 BFS。因此我们可以先使用「并查集」进行预处理，判断「起点」和「终点」是否连通，如果不联通，直接返回 -1−1，有解才调用双向 BFS。
由于使用「并查集」预处理的复杂度与建图是近似的，增加这样的预处理并不会越过我们时空复杂度的上限，因此这样的预处理是有益的。一定程度上可以最大化双向 BFS 减少搜索空间的效益。
网络异常，图片无法展示
|
代码：
class Solution { static int N = (int)1e6+10; static int[] p = new int[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void union(int a, int b) { p[find(a)] = p[find(b)]; } boolean query(int a, int b) { return find(a) == find(b); } int s, t; int[][] rs; public int numBusesToDestination(int[][] _rs, int _s, int _t) { rs = _rs; s = _s; t = _t; if (s == t) return 0; for (int i = 0; i < N; i++) p[i] = i; for (int[] r : rs) { for (int loc : r) { union(loc, r[0]); } } if (!query(s, t)) return -1; int ans = bfs(); return ans; } // 记录某个车站可以进入的路线 Map<Integer, Set<Integer>> map = new HashMap<>(); int bfs() { Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>(); Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); int n = rs.length; for (int i = 0; i < n; i++) { for (int station : rs[i]) { // 将从起点可以进入的路线加入正向队列 if (station == s) { d1.addLast(i); m1.put(i, 1); } // 将从终点可以进入的路线加入反向队列 if (station == t) { d2.addLast(i); m2.put(i, 1); } Set<Integer> set = map.getOrDefault(station, new HashSet<>()); set.add(i); map.put(station, set); } } // 如果「起点所发起的路线」和「终点所发起的路线」有交集，直接返回 1 Set<Integer> s1 = map.get(s), s2 = map.get(t); Set<Integer> tot = new HashSet<>(); tot.addAll(s1); tot.retainAll(s2); if (!tot.isEmpty()) return 1; // 双向 BFS while (!d1.isEmpty() && !d2.isEmpty()) { int t = -1; if (d1.size() <= d2.size()) { t = update(d1, m1, m2, t); } else { t = update(d2, m2, m1, s); } if (t != -1) return t; } return 0x3f3f3f3f; // never } int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other, int target) { // 取出当前所在的路线，与进入该路线所花费的距离 int poll = d.pollFirst(); int step = cur.get(poll); // 遍历该路线所包含的车站 for (int station : rs[poll]) { if (station == target) return step; // 遍历将由该线路的车站发起的路线 Set<Integer> lines = map.get(station); if (lines == null) continue; for (int nr : lines) { if (cur.containsKey(nr)) continue; if (other.containsKey(nr)) return step + other.get(nr); cur.put(nr, step + 1); d.add(nr); } } return -1; } } 复制代码
- 时间复杂度：令路线的数量为 nn，车站的个数为 mm。并查集和建图的时间复杂度为 O(\sum_{i=0}^{n-1} len(rs[i]))O(∑i=0n−1len(rs[i]))；
BFS求最短路径的复杂度为 O(n * m)O(n∗m)。整体复杂度为 O(n * m + \sum_{i=0}^{n-1} len(rs[i]))O(n∗m+∑i=0n−1len(rs[i]))。 - 空间复杂度：O(n * m + \sum_{i=0}^{n-1} len(rs[i]))O(n∗m+∑i=0n−1len(rs[i]))
最后
这是我们「刷穿 LeetCode」系列文章的第 No.815 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
