BFS: búsqueda en anchura en Java

Problema

Seis calles en vez de cuatro

El despachador de la empresa de mensajería quiere una ruta del almacén al hospital con las menos calles. En esta ciudad cada calle significa un semáforo, un giro y una parada, así que el número de calles importa más que los metros.

Un compañero escribió una búsqueda que toma la primera calle libre y sigue hasta llegar. Si se atasca, vuelve atrás y prueba la siguiente:

static List<String> anyRoute(Map<String, List<String>> graph,
        String at, String target, Set<String> seen) {
    if (at.equals(target)) return new ArrayList<>(List.of(at));
    seen.add(at);
    for (String next : graph.get(at)) {
        if (seen.contains(next)) continue;
        List<String> rest = anyRoute(graph, next, target, seen);
        if (rest != null) {
            rest.add(0, at);
            return rest;
        }
    }
    return null;
}

List<String> route = anyRoute(graph, "Almacén", "Hospital", new HashSet<>());
System.out.println(String.join(" → ", route) + ": " + (route.size() - 1) + " calles");

Almacén → Estación → Plaza → Mercado → Parque → Estadio → Hospital: 6 calles

Hay una ruta, pero tiene 6 calles. Mira el mapa de la lección anterior: Almacén → Estación → Plaza → Cine → Hospital son 4. La búsqueda no se equivocó: nunca pidió la más corta, tomó la primera que encontró.

La idea

Una ola desde el almacén

Imagina una ola que sale del almacén. Primero alcanza todas las paradas a una calle. Luego, desde ellas, todas las paradas nuevas a dos calles. Luego tres. Una parada que la ola ya alcanzó está tomada: las olas siguientes no la tocan.

Así, una parada recibe su distancia en el momento en que la ola la toca por primera vez, y esa es la menor posible.

El orden «primero las más cercanas» lo guarda una cola: las paradas encontradas entran por detrás, y la que se atiende sale por delante. Esto es BFS (búsqueda en anchura, en inglés breadth-first search).

dist guarda la distancia de cada parada encontrada. Es también el conjunto de paradas vistas: una parada con dist no entra en la cola por segunda vez.
prev guarda desde dónde se encontró cada parada. Con él se reconstruye después la ruta.

Míralo

Capa por capa

record Search(Map<String, Integer> dist, Map<String, String> prev) {}

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

static List<String> pathTo(Map<String, String> prev,
                           String target) {
    List<String> path = new ArrayList<>();
    String at = target;
    while (at != null) {
        path.add(at);
        at = prev.get(at);
    }
    Collections.reverse(path);
    return path;
}

Paso a paso, en palabras

Empezamos en Almacén: dist = 0, y es la única parada en la cola.
Almacén sale de la cola. Sus vecinos Estación y Mercado son nuevos: dist = 1, prev = Almacén, y entran al final de la cola.
Estación: Almacén ya tiene dist y se salta. Plaza recibe dist = 2.
Mercado también ve Plaza, pero Plaza ya está en la cola con dist = 2. Cada parada entra en la cola solo una vez. Parque: dist = 2.
La capa 2 sale de la cola y abre la capa 3: Cine al otro lado del puente y Estadio. La cola tiene siempre como mucho dos capas, la más cercana delante.
Cine encuentra Hospital: dist = 4. Cuando Estadio también llega, Hospital ya tiene dist: la primera llegada es la más corta.
Alrededor de Hospital no hay nada nuevo. La cola está vacía: cada parada tiene su distancia desde Almacén.
pathTo va hacia atrás por prev: Hospital ← Cine ← Plaza ← Estación ← Almacén. Al revés, esa es la ruta: 4 calles.

El programa ejecuta BFS desde el almacén e imprime la distancia a cada parada y la ruta al hospital:

Search found = bfs(graph, "Almacén");
for (String stop : stops) {
    System.out.println(stop + ": " + found.dist().get(stop));
}
List<String> path = pathTo(found.prev(), "Hospital");
System.out.println(String.join(" → ", path) + ": " + (path.size() - 1) + " calles");

Almacén: 0
Estación: 1
Mercado: 1
Plaza: 2
Parque: 2
Cine: 3
Hospital: 4
Estadio: 3
Almacén → Estación → Plaza → Cine → Hospital: 4 calles

ArrayDeque es una cola: add pone al final, poll saca del principio. Cómo funciona la cola por dentro está en la lección Pila y cola.

Pruébalo

Pon las líneas en orden

Este es el corazón de BFS: una vuelta del bucle. Pon las líneas en orden:

if (dist.containsKey(next)) continue;
dist.put(next, dist.get(stop) + 1);
prev.put(next, stop);
}
String stop = queue.poll();
for (String next : graph.get(stop)) {
queue.add(next);

Pruébalo

Predice la salida

El mismo BFS, pero empieza en el Cine. ¿Qué imprime el programa para Almacén, Estadio y Parque?

Search found = bfs(graph, "Cine");
StringJoiner line = new StringJoiner(" ");
for (String stop : List.of("Almacén", "Estadio", "Parque")) {
    line.add(String.valueOf(found.dist().get(stop)));
}
System.out.println(line);

Respuesta

4 2 3

3 2 3

3 3 4

La idea

La ruta hacia atrás

dist dice cuántas calles hay, pero no cuáles. La ruta está en prev: el Hospital se encontró desde el Cine, el Cine desde la Plaza, la Plaza desde la Estación, la Estación desde el Almacén. El Almacén no tiene prev, porque allí empezó todo.

Por eso la ruta se lee desde atrás: desde el destino por prev hasta el inicio, y se da la vuelta al final.

static List<String> pathTo(Map<String, String> prev,
                           String target) {
    List<String> path = new ArrayList<>();
    String at = target;
    while (at != null) {
        path.add(at);
        at = prev.get(at);
    }
    Collections.reverse(path);
    return path;
}

String at = target;
while (at != null) {
    path.add(at);
    at = ;
}

Más precisamente, para curiosos

Los caminos de prev forman un árbol: cada parada apunta a exactamente otra, aquella desde la que se encontró, y la raíz es el almacén. Se llama árbol de BFS. Cada rama de la raíz a una parada es la ruta más corta hasta ella. Por eso un solo BFS desde el almacén da las rutas más cortas a todas las paradas a la vez, no solo al hospital.

Si una parada nunca se encontró (no hay ruta), no tiene dist. Comprueba eso antes de llamar a pathTo: si no, obtienes una «ruta» de una parada, el propio destino.

La idea

Por qué la primera llegada es la más corta

La cola tiene como mucho dos capas: d y d + 1, con la más cercana delante. Una parada a d + 1 calles se encuentra desde una a d calles, y las paradas a d + 2 llegan solo cuando las de d + 1 empiezan a salir. Así que una parada recibe su dist de la ruta más corta, y cualquier ruta posterior hasta ella es al menos igual de larga y se descarta.

También importa cuándo se marca una parada como vista: al entrar en la cola, no al salir. Si no, la Plaza, que se ve tanto desde la Estación como desde el Mercado, entraría dos veces.

Más precisamente, para curiosos

La demostración en una frase: por inducción sobre d, todas las paradas a distancia d salen de la cola antes que todas las de distancia d + 1, y cada una recibe dist = d. Esto vale solo si cada arista cuesta 1. Si las calles tienen longitudes distintas, menos calles no significa menos metros. Entonces la cola se cambia por una cola de prioridad por la distancia recorrida, y eso es Dijkstra (la lección de Dijkstra de este módulo).

La idea

Cuánto cuesta

Cada parada entra en la cola como mucho una vez y sale una vez. Al salir, mira sus calles. Una calle de doble sentido se ve desde sus dos extremos. En total: V salidas y 2E miradas, O(V + E).

Eso vale para una lista de adyacencia. Con una matriz «quiénes son los vecinos» es la fila entera, y BFS hace V miradas por parada: O(V²). Ejecuta ambos en una ciudad en cuadrícula de n cruces:

BFS con una lista de adyacencia O(n)
BFS con una matriz O(n²)

Algoritmo	n = 10	n = 1000	n = 5000	n = 100.000
BFS con una lista de adyacencia	36	4872	24.716	498.734
BFS con una matriz	110	1.001.000	25.005.000	≈ 10.002.000.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.get(stop) + 1);
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

Se cuenta cada parada que sale de la cola y cada mirada a un vecino. Con 1000 cruces la lista hace 4872 operaciones y la matriz 1 001 000. Con 100 000 cruces la lista hace 498 734, unas 5 por cruce: una salida y hasta 4 calles. La matriz con 5000 ya está en 25 005 000.

Pruébalo

Encuentra el error

Un compañero decidió que la distancia de una parada nueva es «el siguiente número». El programa imprime:

static Search bfs(Map<String, List<String>> graph,
                  String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    Deque<String> queue = new ArrayDeque<>();
    dist.put(start, 0);
    queue.add(start);
    while (!queue.isEmpty()) {
        String stop = queue.poll();
        for (String next : graph.get(stop)) {
            if (dist.containsKey(next)) continue;
            dist.put(next, dist.size());
            prev.put(next, stop);
            queue.add(next);
        }
    }
    return new Search(dist, prev);
}

Almacén: 0
Estación: 1
Mercado: 2
Plaza: 3
Parque: 4
Cine: 5
Hospital: 7
Estadio: 6
Almacén → Estación → Plaza → Cine → Hospital: 4 calles

La ruta es correcta, 4 calles, y aun así el Hospital sale con 7. ¿En qué línea está el error?

Elige la línea con el error.

Más precisamente

La cola en cada lenguaje

ArrayDeque es un búfer circular: add y poll son O(1). LinkedList también es una Queue, pero cada elemento es un nodo aparte y es más lenta. No uses ArrayList con remove(0): mueve todos los elementos restantes, O(n) en cada extracción, y BFS pasa a ser O(V²) incluso con una lista de adyacencia.

Ejercicio

Las capas de la ciudad

Resuelve la tarea en tu editor.

Capas y puentes. Con BFS desde el almacén imprime las paradas por capas (las paradas de cada capa en el orden de stops) y la parada más lejana. Luego cierra los dos puentes: quítalos de la lista de adyacencia, ejecuta BFS otra vez e imprime qué paradas ya no se pueden alcanzar.

String[][] bridges = {
    {"Mercado", "Parque"}, {"Plaza", "Cine"},
};

Capa 0: Almacén
Capa 1: Estación, Mercado
Capa 2: Plaza, Parque
Capa 3: Cine, Estadio
Capa 4: Hospital
Más lejos: Hospital (4 calles)
Sin los puentes no se llega a: Parque, Cine, Hospital, Estadio

Más tareas

La farmacia más cercana. Algunas paradas tienen una farmacia. Ejecuta un BFS que parta de todas las farmacias a la vez (todas están en la cola con dist 0), e imprime para cada parada a cuántas calles queda la más cercana.
Un laberinto de estantes. El almacén es una cuadrícula de estantes (#) y pasillos (.). Encuentra los pasos mínimos de la entrada a la salida, donde los vecinos de una celda son arriba, abajo, izquierda y derecha.
Todas las más cortas. Cuenta cuántas rutas más cortas distintas hay del almacén a cada parada.

Test

Ponte a prueba

1. ¿Por qué la primera ruta por la que BFS llega a una parada es la más corta en calles?Porque BFS prueba todas las rutas y se queda con la más cortaLa cola atiende todas las paradas a d calles antes de llegar a las que están a d + 1Porque los vecinos de la lista están ordenados por distancia

2. Un compañero cambió la cola por una pila: toma la última parada añadida. ¿Qué pasa?El programa se queda en un bucle infinitoNada: el orden no importaEl recorrido ya no va por capas, y dist puede salir mayor que el camino más corto

3. Las calles tienen longitudes en metros. ¿BFS da la ruta más corta en metros?Sí, siempreSí, si la lista de adyacencia también guarda los metrosNo: BFS cuenta calles, cada calle es un paso, por larga que sea

4. ¿Cuánto trabajo hace BFS en una ciudad con V cruces y E calles, guardada como lista de adyacencia?O(V · E)O(V²)O(V + E): cada parada sale una vez, cada calle se mira dos veces

BFS: las menos paradas

Cookies