Sponsored
Sponsored
In this approach, we treat the problem as a graph where each bus route is a node and bus stops are edges connecting these nodes. We will perform a Breadth-First Search (BFS) starting from the source and try to reach the target while counting the number of buses required. The BFS helps in finding the shortest path in terms of the number of bus routes.
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph.
1from collections import defaultdict, deque
2
3def numBusesToDestination(routes, source, target):
4 if source == target:
5 return 0
6
7 stop_to_routes = defaultdict(set)
8 for i, route in enumerate(routes):
9 for stop in route:
10 stop_to_routes[stop].add(i)
11
12 queue = deque([(source, 0)]) # (current_stop, buses_taken)
13 visited_stops = {source}
14 visited_routes = set()
15
16 while queue:
17 stop, buses = queue.popleft()
18 for route in stop_to_routes[stop]:
19 if route in visited_routes:
20 continue
21 visited_routes.add(route)
22 for next_stop in routes[route]:
23 if next_stop == target:
24 return buses + 1
25 if next_stop not in visited_stops:
26 visited_stops.add(next_stop)
27 queue.append((next_stop, buses + 1))
28
29 return -1This code uses Breadth-First Search (BFS) to explore the given routes. A queue is utilized to manage bus stops, beginning at the source, and systematically visit every possible stop until the target is achieved or all possibilities are exhausted. The unique bus stops and routes are tracked to prevent repetition. When the target stop is reached, the code returns the count of buses needed to reach that spot. If the target is unreachable, it returns -1.
For optimization, we can leverage a bidirectional BFS. This technique reduces the breadth by simultaneously exploring from both the source and the target and meeting in the middle. A dual directional expansion can therefore lead to faster convergence in finding the solution.
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph and queue data structures.
1import java.util.*;
2
3
This Java solution uses a bidirectional BFS approach to expedite the search process. By maintaining two BFS searches - one from the source and another from the target - and keeping track of visited stops using sets, the algorithm can detect an intersection far quicker, which represents a viable path from source to target. The method optimally chooses which search side to expand at each step based on queued elements, enhancing performance over standard BFS methods.