Bus Routes

XXX. Minimum Buses to Destination

Breadth-First Search

Graph

Problem Statement:

You are given a list of bus routes where each route is represented as an array of bus stops. Your task is to find the minimum number of buses you need to take to travel from a starting stop S to a destination stop T. If it is impossible to reach the destination, return -1.

Algorithm:

1. Graph Representation:

   Build a graph using a map where each stop points to a list of bus routes that visit that stop. This representation helps quickly find which bus routes can be taken from any given stop.

2. Breadth-First Search (BFS):

   Use BFS to explore the stops. Each node in the BFS represents a bus stop and the number of buses taken to reach that stop. Use a queue to process stops and a set to track visited bus routes to prevent revisiting.

   • If the current stop is the destination T, return the number of buses taken so far.
   • For each bus route passing through the current stop, mark the route as visited and add all stops in the route to the queue with an incremented bus count.
3. Return Result:

   If all stops are processed and the destination is not reached, return -1 to indicate it is impossible to reach the destination.

Complexity:

Time Complexity: O(n * m), where n is the number of bus routes and m is the average number of stops per route. Each stop is processed once, and each route is traversed at most once.
Space Complexity: O(n * m), for storing the graph and the BFS queue.

Java Implementation:

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        // Edge case: If the start and destination are the same, no bus is needed
        if (S == T) return 0;

        // Set to track visited bus routes
        Set visited = new HashSet<>();
        // Map to represent the graph (stop -> list of bus routes that pass through this stop)
        Map> map = new HashMap<>();

        // Build the graph
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                map.putIfAbsent(stop, new ArrayList<>());
                map.get(stop).add(i); // Add the route index to the stop's list
            }
        }

        // Queue for BFS, storing nodes as (stop, depth)
        Queue q = new LinkedList<>();
        q.offer(new Node(S, 0)); // Start BFS from the source stop

        // Perform BFS
        while (!q.isEmpty()) {
            Node curr = q.poll();

            // If we reach the destination stop, return the bus count
            if (curr.stop == T) return curr.depth;

            // Process all bus routes passing through the current stop
            for (int bus : map.getOrDefault(curr.stop, new ArrayList<>())) {
                if (visited.contains(bus)) continue; // Skip already visited routes
                visited.add(bus); // Mark the route as visited

                // Add all stops in the current route to the queue
                for (int nextStop : routes[bus]) 
                    q.offer(new Node(nextStop, curr.depth + 1));
            }
        }

        // If BFS completes without finding the destination, return -1
        return -1;
    }

    // Helper class to represent a node in BFS
    class Node {
        int stop; // The current bus stop
        int depth; // The number of buses taken to reach this stop

        public Node(int stop, int depth) {
            this.stop = stop;
            this.depth = depth;
        }
    }
}