# LeetCode [Hard] Bus Routes | Algorithm — BFS

Full article and Easy read on LeetCode [Hard] Bus Routes | Algorithm — BFS — Hung, Chien-Hsiang | Blog (chienhsiang-hung.github.io).

# Question

# Attempts

# Classic DFS

At first, I came oup with a classic DFS solution.

class Solution:

def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:

adj_map = defaultdict(list)

visited_map = defaultdict(lambda: False) # travers the routes to build a Adj List

for r in routes:

for i in range(len(r)):

# reach the end

if i == len(r)-1:

adj_map[r[i]].append(r[0])

else:

adj_map[r[i]].append(r[i+1]) stack = deque([

(source, 1)

])

while stack:

current, n_bus = stack.popleft()

if current == target:

return n_bus if visited_map[current]:

continue

visited_map[current] = True

# BFS

for i in range( len(adj_map[current]) ):

# Same bus

if i == 0:

stack.append(

(adj_map[current][i], n_bus)

)

# Transfer

else:

stack.append(

(adj_map[current][i], n_bus+1)

)

return -1

Which failed at case like `[[24],[3,6,11,14,22],[1,23,24],[0,6,14],[1,3,8,11,20]], 20, 8`

where you need to know which bus you’re at i.e. stop-1.

Because the part I used `i == 0`

to determine if that’s a **transfer** doesn’t quite fit for case like above.

`# BFS`

for i in range( len(adj_map[current]) ):

# Same bus

if i == 0:

stack.append(

(adj_map[current][i], n_bus)

)

# Transfer

else:

stack.append(

(adj_map[current][i], n_bus+1)

)

Now you need to look closer to the problem and draw the routes. For example `[[24],[3,6,11,14,22],[1,23,24],[0,6,14],[1,3,8,11,20]]`

the first 4 rounds should be:

`20 -> 1 -> 3 -> 8`

1 -> 23 -> 24

3 -> 6

We need to utilize `queue`

to achieve the transfer record like. How? By **traversing the same route first then other branches**. So that queue would be like `[20,1,3,8,11,23,6...]`

.

*What if we have multiple stop to transfer at the first stop?* Let’s say `[[24,20],[3,6,11,14,22],[1,23,24],[0,6,14],[1,3,8,11,20]]`

. Then you need to know where they are by tagging their `bus_num`

in the `adj_list`

.

# Remember The Bus Number

class Solution:

def numBusesToDestination(self, routes, source: int, target: int) -> int:

adj_map = defaultdict(list)

visited_map = defaultdict(lambda: False) # travers the routes to build a Adj List

for bus_num in range(len(routes)):

for n_stop in range(len(routes[bus_num])):

next_stop_i = (n_stop +1) % len(routes[bus_num])

next_stop = routes[bus_num][next_stop_i] adj_map[ routes[bus_num][n_stop] ].append( (next_stop, bus_num) )

# Example of adj_map

# {

# 1: [(23, 2), (3, 4)],

# }

stop_queue = deque([

( source, adj_map[source][0][1] )

])

buses = set()

while stop_queue:

current, cur_bus_num = stop_queue.popleft()

if visited_map[current]: continue visited_map[current] = True

buses.add(cur_bus_num)

if current == target: return len(buses) for next_stop, next_bus_num in adj_map[current]:

if next_bus_num == cur_bus_num:

stop_queue.appendleft(

(next_stop, next_bus_num)

)

else:

stop_queue.append(

(next_stop, next_bus_num)

)

return -1

Failed at **Input**:

`[[1,9,12,20,23,24,35,38],[10,21,24,31,32,34,37,38,43],[10,19,28,37],[8],[14,19],[11,17,23,31,41,43,44],[21,26,29,33],[5,11,33,41],[4,5,8,9,24,44]]`

,`source=37`

, `target=28`

Dry run the code you will find the issue here: **How can we find the shortest route (in terms of number of transfer needed)?** *(Since the output was 4 and expected is 1.)*

# Find The Shortest Route (Transfer)

You will need to divide the searching route and record it and find the `min`

.

class Solution:

def numBusesToDestination(self, routes, source: int, target: int) -> int:

adj_map = defaultdict(list)

visited_map = defaultdict(lambda: False) # travers the routes to build a Adj List

for bus_num in range(len(routes)):

for n_stop in range(len(routes[bus_num])):

next_stop_i = (n_stop +1) % len(routes[bus_num])

next_stop = routes[bus_num][next_stop_i] adj_map[ routes[bus_num][n_stop] ].append( (next_stop, bus_num) )

transfers = []

def search(current, current_bus_num, target, n_transfer=1):

if current == target:

transfers.append(n_transfer)

return if visited_map[current]:

return

visited_map[current] = True for next_stop, next_bus_num in adj_map[current]:

if current_bus_num == next_bus_num:

search(next_stop, next_bus_num, target, n_transfer)

else:

search(next_stop, next_bus_num, target, n_transfer+1)

visited_map[source] = True

for next_stop, bus_num in adj_map[source]:

search(next_stop, bus_num, target) return -1 if not transfers else min(transfers)

Then I proposed the new solution with **num of transfers recorded** while failed at case like `[[10,21,24,31,32,34,37],[10,19,28,37],[11,17,23,31,41,43,44],[21,26,29,33],[5,11,33,41],[4,5,8,9,24,44]]`

, `output=2`

, `expected=1`

. You need to be careful of adapting **1D visited record or 2D**.

# 2D Visited Matrix

class Solution:

def numBusesToDestination(self, routes, source: int, target: int) -> int:

adj_map = defaultdict(list)

# prepare a 2-d visited matrix

visited_map = [

[False] * len(routes[i]) for i in range(len(routes))

] # travers the routes to build a Adj List

for bus_num in range(len(routes)):

for n_stop in range(len(routes[bus_num])):

next_stop_i = (n_stop +1) % len(routes[bus_num])

next_stop = routes[bus_num][next_stop_i] adj_map[ routes[bus_num][n_stop] ].append( (next_stop, bus_num, n_stop) ) # init source visited

if n_stop == source:

visited_map[bus_num][n_stop] = True

transfers = []

def search(current, current_bus_num, n_stop, target, n_transfer=1):

if current == target:

transfers.append(n_transfer)

return if visited_map[current_bus_num][n_stop]:

return

visited_map[current_bus_num][n_stop] = True for next_stop, next_bus_num, n_stop in adj_map[current]:

if current_bus_num == next_bus_num:

search(next_stop, next_bus_num, n_stop, target, n_transfer)

else:

search(next_stop, next_bus_num, n_stop, target, n_transfer+1)

for next_stop, bus_num, n_stop in adj_map[source]:

search(next_stop, bus_num, n_stop, target) return -1 if not transfers else min(transfers)

With the *2-d visited matrix*, still I got the wrong output. After a further examination, I’ve found I’ve might been using the wrong technique. I should have adopted **BFS** instead of **DFS** which made my visited matrix useless here (sine it needs to be updated/re-initialized on each branch).

**You need to do BFS simultaniously.**

To record the visited-matrix in order to determine whether to stop or not.

`class Solution:`

def numBusesToDestination(self, routes, source: int, target: int) -> int:

if source == target:

return 0

adj_map = defaultdict(list)

# traverse the routes to build a Adj List

for bus_num in range(len(routes)):

for n_stop in range(len(routes[bus_num])):

next_stop_i = (n_stop +1) % len(routes[bus_num])

next_stop = routes[bus_num][next_stop_i]

adj_map[ routes[bus_num][n_stop] ].append( (next_stop, bus_num) )

transfers = []

def search(current, current_bus_num, visited, target, n_transfer=1):

if current == target:

transfers.append(n_transfer)

return

elif visited[current]:

return

visited[current] = True

# Traverse

for next_stop, next_bus_num in adj_map[current]:

if current_bus_num == next_bus_num:

search(next_stop, next_bus_num, visited.copy(), target, n_transfer)

else:

search(next_stop, next_bus_num, visited.copy(), target, n_transfer+1)

for next_stop, bus_num in adj_map[source]:

visited = defaultdict(lambda: False)

visited[source] = True

search(next_stop, bus_num, visited, target)

return -1 if not transfers else min(transfers)

Still failed, at

`# failed at `

test1 = [[3,16,33,45,59,79,103,135],[3,35,39,54,56,78,96,101,120,132,146,148],[13,72,98],[37,70,107],[0,12,31,37,41,68,78,94,100,101,113,123],[11,32,52,85,135],[43,50,128],[0,13,49,51,53,55,60,65,66,80,82,87,92,99,112,118,120,125,128,131,137],[15,19,34,37,45,52,56,97,108,123,142],[7,9,20,28,29,33,34,38,43,46,47,48,53,59,65,72,74,80,88,92,110,111,113,119,135,140],[15,41,64,83],[7,13,26,31,57,85,101,108,110,115,119,124,149],[47,61,67,70,74,75,77,84,92,101,124,132,133,142,147],[0,2,5,6,12,18,34,37,47,58,77,98,99,109,112,131,135,149],[6,7,8,9,14,17,21,25,33,40,45,50,56,57,58,60,68,92,93,100,108,114,130,149],[7],[5,16,22,48,77,82,108,114,124],[34,71],[8,16,32,48,104,108,116,134,145],[3,10,16,19,35,45,64,74,89,101,116,149],[1,5,7,10,11,18,40,45,50,51,52,54,55,69,71,81,82,83,85,89,96,100,114,115,124,134,138,148],[0,2,3,5,6,9,15,52,64,103,108,114,146],[5,33,39,40,44,45,66,67,68,69,84,102,106,115,120,128,133],[17,26,49,50,55,58,60,65,88,90,102,121,126,130,137,139,144],[6,12,13,37,41,42,48,50,51,55,64,65,68,70,73,102,106,108,120,123,126,127,129,135,136,149],[6,7,12,33,37,41,47,53,54,80,107,121,126],[15,75,91,103,107,110,125,139,142,149],[18,24,30,52,61,64,75,79,85,95,100,103,105,111,128,129,142],[3,14,18,32,45,52,57,63,68,78,85,91,100,104,111,114,142],[4,7,11,20,21,31,32,33,48,61,62,65,66,73,80,92,93,97,99,108,112,116,136,139]]

# 85

# 112

# output=4, expected=2

We need to re-think the problem, how do we walk through the routes? Or in other words, how do we travel from a to b by bus if we have no maps?

# Why BFS

In order to record the right process. Imagine you’re taking a bus, you have tried all the bus on that specific station. Would you come back again before you reach the end given the condition that you have travelled all the possible routes starts from this station? *(Inspired by **zippysphinx**’s **Solution**.)*

class Solution:

def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:

transfers = 0

if source == target:

return transfers # create a stop-to-buses map

stop_to_bus = defaultdict(set)

for bus_num in range(len(routes)):

for i in range(len(routes[bus_num])):

stop_to_bus[routes[bus_num][i]].add(bus_num)

visited_buses = [False] * len(routes)

bus_queue = deque([

stop_to_bus[source] # set of buses

])

while bus_queue[0]:

current_buses = bus_queue.popleft()

transfers += 1

bus_queue.append(set())

for bus in current_buses:

visited_buses[bus] = True

for stop in routes[bus]:

if stop == target:

return transfers # add new bus to visit

for next_bus in stop_to_bus[stop]:

if not visited_buses[ next_bus ]:

bus_queue[-1].add( next_bus )

return -1