Breadth-First Search
Bus Routes
hard
Count: 10
DESCRIPTION (inspired by Leetcode.com)
You are given a 2D-integer array routes representing bus routes where routes[i] is a list of stops that the i-th bus makes. For example, if routes[0] = [3, 8, 9], it means the first bus goes through stops 3, 8, 9, 3, 8, 9, continuously.
You are also given two integers source and target, representing the starting bus stop and the destination bus stop, respectively. Write a function that takes in routes, source, and target as input, and returns the minimum number of buses you need to take to travel from source to target. Return -1 if it is not possible to reach the destination.
Example 1:
Input:
routes = [[3, 8, 9], [5, 6, 8], [1, 7, 10]] source = 3 target = 6
Output: 2
Explanation: You can take the first bus from stop 3 to stop 8, and then take the second bus from stop 8 to stop 6.
Example 2:
Input:
routes = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]] source = 1 target = 12
Output: -1 (It is not possible to reach the destination)
Explanation
Since this question involves finding the shortest distance in a graph, we should use a breadth-first search (BFS) traversal to solve it.
The key to this question is in how we model the problem as a graph problem. Let's first visualize how we can use BFS to find the shortest path between two bus stops.
If we let the nodes of our graph be the bus routes, then the neighbors of each node are the other bus routes that share a stop with the current bus route.
For example, if we have the following bus routes:
routes = [[2, 3, 8], [3, 4, 7], [6, 4]]then we can visualize the resulting graph below:
Node "2-3-8", which represents route[0], is connected by an edge to node "3-4-7" because they share a stop at 3. Node "6-4" is also connected by an edge to node "3-4-7" because they share a stop at 4.
Visualizing this graph helps us understand how we can use BFS to find the shortest path between two bus stops. We can start our BFS at the node containing source, and use BFS to repeatedly visiting neighboring nodes until we reach the node containing target.
Representing the Graph
We can represent our graph as an adjacency list. Since each node in our graph is a bus route, we can represent using the index of the bus route in the routes list.
But rather than storing the bus route indexes as the keys in our adjacency list, we'll use the bus stops themselves as the keys. This makes it easier to build our adjacency list - we can simply iterate over each stop in each bus route, and add the bus route index to the adjacency list for that stop.
Then, if we have the index of a bus route, we can find its neighbors by iterating over each stop in that bus route, and looking up the bus routes that share that stop in our adjacency list.
This is easier to understand with an example. Let's walkthrough the solution with the following input:
Walkthrough
Let's walkthrough each step of the solution when we have the following input:
routes = [[2, 3, 8], [3, 4, 7], [6, 4]]
source = 2
target = 6Step 1: Initialize the Graph
We start by building the graph from the input routes. We create an adjacency list where each key is a bus stop and the value is a list of bus routes (indexes) that stop at that bus stop. These are the edges in our graph.
For this input, the adjacency list would look like:
{
2: [0],
3: [0, 1],
8: [0],
4: [1, 2],
7: [1],
6: [2]
}So if we wanted to find the neighbors of bus route 0, we would look up the stops 2, 3, and 8 (routes[0]) in the adjacency list, and see that stop 3 is connected to bus route 1.
Step 2: Initialize the Queue and Visited Set
Each node in our graph is a bus route, so we'll start by initializing our BFS queue with the index of all bus routes that contain the source bus stop, and the number of bus routes taken so far. We also initialize a set to keep track of the bus routes we have visited, so that we don't revisit them (to avoid infinite loops).
In this case, source is 2, which is contained only on bus route 0. So, we initialize our queue and our visited set:
queue = [(0, 1)] # (index of bus route, number of bus routes taken)
visited = { 0 } # set of visited bus routesStep 3: Perform BFS Traversal
Now, we're ready to perform the BFS traversal. We'll repeatedly dequeue from the front of the queue. Each time we dequeue, we get the current bus route and the number of bus routes taken so far, which are:
curr_bus = 0 # current bus route index
num_changes = 1 # number of bus routes taken so farNow, we loop over all the bus stops contained in the current bus route route[curr_bus]. We check if any of these bus stops are the target bus stop. If we find the target bus stop, that means we can reach our destination without having to take another bus, so we return the number of bus routes taken so far immediately.
Otherwise, we need to continue searching by adding the neighboring bus routes to our queue.
Adding Neighbors to the Queue
If the target bus stop is not found, we then check if any of the bus stops in the current bus route are connected to other bus routes by checking our adjacency list from Step 1 and have not been visited yet. If that is true, we add that bus route to the queue along with the number of bus routes taken so far plus one. We also mark the bus route as visited.
In this case, bus stop 3 is connected to bus route 1, so we add that to the queue, and mark it as visited:
queue = [(1, 2)] # (index of bus route, number of bus routes taken)
visited = { 0, 1 } # set of visited bus routesThis continues until we find the target bus stop or until the queue is empty.
Solution
from collections import dequeclass Solution:def bus_routes(self, routes, source, target):if source == target:return 0# Create a dictionary mapping bus top to bus route index# These are the edges in our graphbus_stops = {}for i, route in enumerate(routes):for stop in route:if stop not in bus_stops:bus_stops[stop] = []bus_stops[stop].append(i)if source not in bus_stops:return -1visited = set()queue = deque()# Step 2: Initialize BFS queue and visited setfor bus in bus_stops.get(source, []):queue.append((bus, 1))visited.add(bus)while queue:curr_bus, num_changes = queue.popleft()# check if any of the bus stops in# the current route is the targetfor stop in routes[curr_bus]:if stop == target:return num_changes# add neighbors to the queuefor connected_bus in bus_stops[stop]:if connected_bus not in visited:queue.append((connected_bus, num_changes + 1))visited.add(connected_bus)return -1 # No possible route found
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(S + R²) where S is the total number of stops across all routes and R is the number of routes. Building the adjacency list takes O(S) time. In the worst case, BFS visits all routes and for each route, we check all its stops against all other routes, leading to O(R²) behavior.
Space Complexity: O(S + R) where S is the total number of stops and R is the number of routes. We store an adjacency list mapping stops to routes O(S), plus the BFS queue and visited set which can each contain at most R routes.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.