BFS經典應用 最精簡公車路線搭乘次數 Bus Routes_Leetcode #815
題目敘述
題目會給我們一個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^50 <= routes[i][j] < 10^60 <= 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
