【图论搜索专题】并查集优化双向 BFS
题目描述
这是 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^5
- routes[i] 中的所有值 互不相同
- sum(routes[i].length) <=10^5
- 0 <= routes[i][j] <10^6
- 0 <= source, target <10^6
基本分析
为了方便，我们令每个公交站为一个「车站」，由一个「车站」可以进入一条或多条「路线」。
问题为从「起点车站」到「终点车站」，所进入的最少路线为多少。
抽象每个「路线」为一个点，当不同「路线」之间存在「公共车站」则为其增加一条边权为 1 的无向边。
单向 BFS
由于是在边权为 1 的图上求最短路，我们直接使用 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;
}
}
- 时间复杂度：令路线的数量为 n ，车站的数量为 m 。建图的时间复杂度为 O(\sum_{i=0}^{n-1} len(rs[i])) ；
BFS部分每个路线只会入队一次，最坏情况下每个路线都包含所有车站，复杂度为 O(n * m) 。整体复杂度为 O(n * m + \sum_{i=0}^{n-1} len(rs[i])) 。 - 空间复杂度：O(n * m)
双向 BFS（并查集预处理无解情况）
另外一个做法是使用双向 BFS。
首先建图方式不变，将「起点」和「终点」所能进入的路线分别放入两个方向的队列，如果「遇到公共的路线」或者「当前路线包含了目标位置」，说明找到了最短路径。
另外我们知道，双向 BFS 在无解的情况下不如单向 BFS。因此我们可以先使用「并查集」进行预处理，判断「起点」和「终点」是否连通，如果不联通，直接返回 -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 res = -1;
if (d1.size() <= d2.size()) {
res = update(d1, m1, m2);
} else {
res = update(d2, m2, m1);
}
if (res != -1) return res;
}
return 0x3f3f3f3f; // never
}
int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other) {
// 取出当前所在的路线，与进入该路线所花费的距离
int poll = d.pollFirst();
int step = cur.get(poll);
// 遍历该路线所包含的车站
for (int station : rs[poll]) {
// 遍历将由该线路的车站发起的路线
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;
}
}
- 时间复杂度：令路线的数量为 n ，车站的个数为 m 。并查集和建图的时间复杂度为 O(\sum_{i=0}^{n-1} len(rs[i])) ；
BFS求最短路径的复杂度为 O(n * m) 。整体复杂度为 O(n * m + \sum_{i=0}^{n-1} len(rs[i])) 。 - 空间复杂度：O(n * m + \sum_{i=0}^{n-1} len(rs[i]))
最后
这是我们「刷穿 LeetCode」系列文章的第 No.815 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
