返回
Featured image of post LeetCode 815 - 公交路线
Leetcode

LeetCode 815 - 公交路线

BFS与图压缩.

[LeetCode] 815. Bus Routes

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example 1:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2:

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Constraints:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 10^5
  • All the values of routes[i] are unique.
  • sum(routes[i].length) <= 10^5
  • 0 <= routes[i][j] < 10^6
  • 0 <= source, target < 10^6

顺便贴一下两年前这道题的提示：

  • Note:
    • 1 <= routes.length <= 500.
    • 1 <= routes[i].length <= 500.
    • 0 <= routes[i][j] < 10 ^ 6.

题解 图压缩 + 最短路径算法

类似题：LeetCode 127 Word Ladder II

看一下两年前和现在对案例限制的不同就可以看出来——力抠把这道题图的成分提升了，并且告诉你了一条公交路线里不会有重复站点，最终要的是，明确了公交站台的数量远远高于公交线路的数量（最离谱的是最后一个案例，尼玛十几条公交线路总共经过了五六万个站，要是在城市天际线里搞这种线路，小人上班还没坐到单位就老死了好吗），换句话说，如果不进行压缩，直接以公交站为结点进行 BFS ，你的图会相当大，如果压缩了，那效率上一定是有收益的。因此有必要将站台图压缩成公交线路的邻接图。

int n = routes.length;
boolean[][] edge = new boolean[n][n];
Map<Integer, List<Integer>> rec = new HashMap<>();
for (int i = 0; i < n; i++) {
    for (int site : routes[i]) {
        List<Integer> list = rec.getOrDefault(site, new ArrayList<>());
        for (int j : list) {
            edge[i][j] = edge[j][i] = true;
        }
        list.add(i);
        rec.put(site, list);
    }
}

这样下来，在搜索过程中队列中保存的就都是公交路线号而不是站台号了，那么起点和终点也就不是站台，而是经过相应站台所有公交线路的集合了，这其实就和 127 题那个单词编辑步长特别相似了，用 BFS 应当是可以的，而且其实这里的公交都是环线，完全可以用双向 BFS 进行优化（当发现一道 BFS 题的起点和终点可以互换，换句话说图是无向的，基本都可以用上双向 BFS）。

然而官答这里直接当成图来做了，直接算了个到所有（除经过起始站的之外）其它公交线路的最少转车站数，用的还是 SPFA，考虑到最后判题案例中其实充斥的都是站点繁多但实际上连通却不多的稀疏图，这样的选择反而相当高效。所以说合适的输入案例是最有效的优化。

虽然 OJ 里无环的情况下还是迪杰斯特拉稳妥一些，但 Leetcode 上基本 SPFA 完全没有问题，写起来还方便，直接用队列不断更新相邻结点的最小距离，一旦距离进行更新就将该结点也丢进队列里，继续更新，直到队列为空。这一算法在稀疏图中效率非常高。

得到的结果里去找能到终点的最小距离就行了，整个算法理解起来非常简单。

int[] dis = new int[n];
Arrays.fill(dis, -1);
Queue<Integer> que = new ArrayDeque<>();
for (int site : rec.getOrDefault(source, new ArrayList<>())) {
    dis[site] = 1;
    que.offer(site);
}
while (!que.isEmpty()) {
    int x = que.poll();
    for (int y = 0; y < n; y++) {
        if (edge[x][y] && dis[y] == -1) {
            dis[y] = dis[x] + 1;
            que.offer(y);
        }
    }
}
int ret = Integer.MAX_VALUE;
for (int site : rec.getOrDefault(target, new ArrayList<>())) {
    if (dis[site] != -1) {
        ret = Math.min(ret, dis[site]);
    }
}
return ret == Integer.MAX_VALUE ? -1 : ret;

代码总和

public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) {
        return 0;
    }
    int n = routes.length;
    boolean[][] edge = new boolean[n][n];
    Map<Integer, List<Integer>> rec = new HashMap<>();
    for (int i = 0; i < n; i++) {
        for (int site : routes[i]) {
            List<Integer> list = rec.getOrDefault(site, new ArrayList<>());
            for (int j : list) {
                edge[i][j] = edge[j][i] = true;
            }
            list.add(i);
            rec.put(site, list);
        }
    }

    int[] dis = new int[n];
    Arrays.fill(dis, -1);
    Queue<Integer> que = new ArrayDeque<>();
    for (int site : rec.getOrDefault(source, new ArrayList<>())) {
        dis[site] = 1;
        que.offer(site);
    }
    while (!que.isEmpty()) {
        int x = que.poll();
        for (int y = 0; y < n; y++) {
            if (edge[x][y] && dis[y] == -1) {
                dis[y] = dis[x] + 1;
                que.offer(y);
            }
        }
    }
    int ret = Integer.MAX_VALUE;
    for (int site : rec.getOrDefault(target, new ArrayList<>())) {
        if (dis[site] != -1) {
            ret = Math.min(ret, dis[site]);
        }
    }
    return ret == Integer.MAX_VALUE ? -1 : ret;
}

题解 BFS

这里再写一个双向 BFS 。压缩部分和前面是一样的，问题是搜索部分。

首先，将起点和终点（其实是经过起点和终点的所有公交线路）分别装入两个方向的 BFS 队列中，如果这里就发现有一样的，那说明有车能从起点直达终点，不用搜了，直接输出 1 。

boolean[] vis = new boolean[n];
Deque<Integer> src_q, des_q;
List<Integer> tar = rec.get(source);
if (tar == null) {
    return -1;
} else {
    src_q = new ArrayDeque<>(tar);
    for (Integer i : tar) {
        vis[i] = true;
    }
}
tar = rec.get(target);
if (tar == null) {
    return -1;
} else {
    des_q = new ArrayDeque<>(tar);
    for (Integer i : tar) {
        if (vis[i])
            return 1;
        else
            vis[i] = true;
    }
}

接下来就是双向 BFS，既然是 BFS，我们每次走一步，搜一步能到的所有公交线路，如果搜到路线出现在另一方向的队列中，说明两个队列接上了，直接输出。

int src_steps = 0, des_steps = 1;
while (!src_q.isEmpty() && !des_q.isEmpty()) {
    Deque<Integer> front, back;
  
  	// 每次挑元素少的队列进行 BFS，从而收缩搜索范围
    if (src_q.size() > des_q.size()) {
        front = des_q;
        back = src_q;
        ++des_steps;
    } else {
        front = src_q;
        back = des_q;
        ++src_steps;
    }
  
  	// 检查邻结点中有没有能到对面（即另一个方向的队列）
    for (int i = front.size(); i > 0; --i) {
        int t = front.removeFirst();
        for (int j = 0; j < n; ++j) {
            if (edge[t][j] && !vis[j]) {
                if (!vis[j]) {
                    vis[j] = true;
                    front.addLast(j);
                } else {
                    if (back.contains(j)) {
                        return src_steps + des_steps;
                    }
                }
            }
        }
    }
}
return -1;

代码总和

public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) {
        return 0;
    }
    int n = routes.length;
    boolean[][] edge = new boolean[n][n];
    Map<Integer, List<Integer>> rec = new HashMap<>();
    for (int i = 0; i < n; i++) {
        for (int site : routes[i]) {
            List<Integer> list = rec.getOrDefault(site, new ArrayList<>());
            for (int j : list) {
                edge[i][j] = edge[j][i] = true;
            }
            list.add(i);
            rec.put(site, list);
        }
    }
    boolean[] vis = new boolean[n];
    Deque<Integer> src_q, des_q;
    List<Integer> tar = rec.get(source);
    if (tar == null) {
        return -1;
    } else {
        src_q = new ArrayDeque<>(tar);
        for (Integer i : tar) {
            vis[i] = true;
        }
    }
    tar = rec.get(target);
    if (tar == null) {
        return -1;
    } else {
        des_q = new ArrayDeque<>(tar);
        for (Integer i : tar) {
            if (vis[i])
                return 1;
            else
                vis[i] = true;
        }
    }
    int src_steps = 0, des_steps = 1;
    while (!src_q.isEmpty() && !des_q.isEmpty()) {
        Deque<Integer> front, back;
        if (src_q.size() > des_q.size()) {
            front = des_q;
            back = src_q;
            ++des_steps;
        } else {
            front = src_q;
            back = des_q;
            ++src_steps;
        }
        for (int i = front.size(); i > 0; --i) {
            int t = front.removeFirst();
            for (int j = 0; j < n; ++j) {
                if (edge[t][j]) {
                    if (!vis[j]) {
                        vis[j] = true;
                        front.addLast(j);
                    } else {
                        if (back.contains(j)) {
                            return src_steps + des_steps;
                        }
                    }
                }
            }
        }
    }
    return -1;
}

总结

这道题反正无论如何都绕不开图压缩了。搜索上，两种方法最终时间相差无几（指用 Leetcode 案例前提下），最小路径算法其实有些超过题目需求了，不过 SPFA 很契合这道题的场景，因此效率还是很高，加上写起来方便（重点），略优于双向 BFS。

comments powered by Disqus
© 2020 - 2024 图拉国营噄茶馆