BFS經典應用 最精簡公車路線搭乘次數 Bus Routes_Leetcode #815

這題的題目在這裡:Bus Routes

題目敘述

題目要求我們計算出，從起點站source到終點站target的最精簡公車路線搭乘次數是幾次?

也就是說，就是在最少轉乘的前提下，旅途中需要搭乘幾條公車路線?

如果無法抵達，則返回-1

測試範例

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

演算法

這一題可以用圖論的最短路徑演算法來解題。

怎麼說呢?

可以把同一條路線上的公車站都是為同一個虛擬節點。

公車路線#0 整個視為一體，視為虛擬節點0。

公車路線#1 整個視為一體，視為虛擬節點1。

...

其餘依此類推

當兩條公車路線有交會在某個公車站時，則兩個虛擬節點有一條邊相連，成本為1，對應到一次轉乘，也就是多一次乘車次數。

因為每次轉乘的成本都相同，都是累加次數一次，所以這裡可以使用BFS廣度優先演算法來找最小公車路線搭乘次數。

以起點為出發點，搭乘次數為0次，每踏上一條新的公車路線，路線搭乘次數就+1。

以搭乘公車路線的總次數為層數，由內而外，從1層往外擴散到2層、第3層...依此類推

BFS迭代中，當公車站牌為終點時，此時的擴散層數就是最小公車路線搭乘次數。

BFS迭代結束後，若仍無法抵達終點，則返回-1，代表無解。

程式碼

class Solution:
　def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
　　
　　if source == target:
　　　# Quick response to simple case
　　　# No need to take bus if source is equal to target
　　　return 0

　　# key: bus_stop
　　# value: busline to corresponding bus_stop
　　bus_info = defaultdict(list)

　　for busline, route in enumerate(routes):
　　　for bus_stop in route:
　　　　bus_info[bus_stop].append(busline)
　　　　
　　travel_queue = deque( [(source, 0)] )
　　visited = set([source])
　　bus_line_considered = set()

　　# Find shortest bus transfer count from Source to Target
　　while travel_queue:
　　　
　　　cur_bus_stop, get_on_bus_count = travel_queue.popleft()

　　　if cur_bus_stop == target: return get_on_bus_count

　　　for busline in bus_info[cur_bus_stop]:
　　　　
　　　　if busline in bus_line_considered:
　　　　　continue

　　　　for other_bus_stop in routes[busline]:
　　　　　if other_bus_stop not in visited:
　　　　　　travel_queue.append((other_bus_stop, get_on_bus_count + 1))
　　　　　　visited.add(other_bus_stop)
　　　　
　　　　# This busline has been considered, clear to empty to avoid repetition
　　　　#routes[busline] = []
　　　　bus_line_considered.add(busline)

　　return -1

複雜度分析

時間複雜度:

最差情況，發生在每個車站都被每條路線包含。

此時建表bus_info的時間成本最大，需耗費O( bus stop count * bust line count)

空間複雜度:

最差情況，發生在每個車站都被每條路線包含。

此時建表bus_info的空間成本最大，需耗費O( bus stop count * bust line count)

關鍵知識點

可以把同一條路線上的公車站都是為同一個虛擬節點。

當兩條公車路線有交會在某個公車站時，則兩個虛擬節點有一條邊相連，成本為1，對應到一次轉乘，也就是多一次乘車次數。

因為每次轉乘的成本都相同，都是累加次數一次，所以這裡可以使用BFS廣度優先演算法來找最小公車路線搭乘次數。

Reference:

[1] Python O(m*n) by BFS [+ Visualization] - Bus Routes - LeetCode