0815. Bus Routes

# 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:

``````Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 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.
``````

Note:

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

## 题目大意 #

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

## 解题思路 #

• 给出一些公交路线，公交路径代表经过的哪些站。现在给出起点和终点站，问最少需要换多少辆公交车才能从起点到终点？
• 这一题可以转换成图论的问题，将每个站台看成顶点，公交路径看成每个顶点的边。同一个公交的边染色相同。题目即可转化为从顶点 S 到顶点 T 需要经过最少多少条不同的染色边。用 BFS 即可轻松解决。从起点 S 开始，不断的扩展它能到达的站点。用 visited 数组防止放入已经可达的站点引起的环。用 map 存储站点和公交车的映射关系(即某个站点可以由哪些公交车到达)，BFS 的过程中可以用这个映射关系，拿到公交车的其他站点信息，从而扩张队列里面的可达站点。一旦扩展出现了终点 T，就可以返回结果了。

## 代码 #

``````
package leetcode

func numBusesToDestination(routes [][]int, S int, T int) int {
if S == T {
return 0
}
// vertexMap 中 key 是站点，value 是公交车数组，代表这些公交车路线可以到达此站点
vertexMap, visited, queue, res := map[int][]int{}, make([]bool, len(routes)), []int{}, 0
for i := 0; i < len(routes); i++ {
for _, v := range routes[i] {
tmp := vertexMap[v]
tmp = append(tmp, i)
vertexMap[v] = tmp
}
}
queue = append(queue, S)
for len(queue) > 0 {
res++
qlen := len(queue)
for i := 0; i < qlen; i++ {
vertex := queue[0]
queue = queue[1:]
for _, bus := range vertexMap[vertex] {
if visited[bus] == true {
continue
}
visited[bus] = true
for _, v := range routes[bus] {
if v == T {
return res
}
queue = append(queue, v)
}
}
}
}
return -1
}

``````

Apr 8, 2023