DFS: búsqueda en profundidad en Java

Problema

Una ciudad cortada por el río

La ciudad cierra los dos puentes por obras. Los mensajeros ya no pueden cruzar el río, y quien coordina el reparto tiene que saber en cuántas partes se parte la ciudad y qué paradas hay en cada parte: cada parte la atenderá una furgoneta distinta.

De la lección de BFS sabes cómo encontrar lo que se alcanza desde el almacén. Pero puede haber muchas partes, y cada una hay que encontrarla entera. Necesitas un recorrido que empiece en cada parada que aún no tenga parte y marque todo lo que alcanza.

En la misma ciudad hay un segundo problema. El plan de reparto tiene reglas «A se entrega antes que B». Alguien añadió una regla equivocada y ahora no hay ningún orden que las cumpla todas. ¿Qué regla tiene la culpa?

La idea

Hasta donde llega la calle

DFS (búsqueda en profundidad) camina como una persona en un laberinto: toma la primera calle hacia una parada desconocida, desde ahí la primera hacia la siguiente desconocida, y así hasta llegar a una parada alrededor de la cual todo se ha visto. Entonces vuelve atrás una parada y prueba la siguiente calle de esa parada.

Con recursión, volver atrás ocurre solo: visit de una parada llama a visit para su primer vecino desconocido, y cuando ese termina, el bucle sigue con el siguiente. La pila de llamadas recuerda hasta dónde ha llegado cada parada.

Cada parada recibe el número de su isla en cuanto se entra en ella. Eso es también el conjunto de las paradas vistas: una parada con número no se visita por segunda vez.
Una isla (una componente conexa) es todo lo que alcanza un visit. El bucle sobre todas las paradas lanza un visit nuevo desde cada parada sin número.

Míralo

Hacia abajo y de vuelta

static void visit(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island, islandOf);
        }
    }
}

static Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : stops) {
        if (islandOf.containsKey(stop)) continue;
        count++;
        visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

static void visit(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island, islandOf);
        }
    }
}

static Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : stops) {
        if (islandOf.containsKey(stop)) continue;
        count++;
        visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

Paso a paso, en palabras

Los dos puentes están cerrados. islands recorre las paradas en orden: Almacén aún no tiene isla, así que count = 1 y visit arranca desde ahí.
visit(Almacén) le da la isla 1 y baja enseguida al primer vecino sin isla: Estación. Almacén espera en gris en la pila de llamadas.
Cada vez más hondo: Estación → Plaza → Mercado. Hay cuatro llamadas abiertas a la vez y cada una espera a la de arriba.
Alrededor de Mercado todo tiene ya una isla. visit vuelve y Mercado pasa a negro. De vuelta por la pila: en Plaza y en Estación tampoco hay nada nuevo.
Almacén vuelve a estar arriba. Su último vecino Mercado ya está visto y el primer recorrido termina: la isla 1 es Almacén, Estación, Mercado, Plaza. Los puentes cerrados lo han detenido en el río.
El bucle de islands continúa: Estación, Mercado y Plaza ya tienen isla y se saltan. Parque no tiene: count = 2.
El mismo recorrido en la otra orilla: Parque → Estadio → Hospital → Cine, luego atrás hasta Parque.
Dos islas: 4 paradas en cada orilla. Cada parada recibió un número una vez y cada calle se miró desde sus dos extremos: O(V + E).

El programa cierra los puentes, lanza islands e imprime las islas:

String[][] closed = {
    {"Mercado", "Parque"}, {"Plaza", "Cine"},
};
for (String[] street : closed) {
    graph.get(street[0]).remove(street[1]);
    graph.get(street[1]).remove(street[0]);
}
Map<String, Integer> islandOf = islands(graph, stops);
int count = Collections.max(islandOf.values());
System.out.println("Islas: " + count);
for (int i = 1; i <= count; i++) {
    List<String> members = new ArrayList<>();
    for (String stop : stops) {
        if (islandOf.get(stop) == i) members.add(stop);
    }
    System.out.println("Isla " + i + ": " + String.join(", ", members));
}

Islas: 2
Isla 1: Almacén, Estación, Mercado, Plaza
Isla 2: Parque, Cine, Hospital, Estadio

El número de la isla se guarda en un HashMap<String, Integer>, y su cantidad es el mayor número que hay en él.

Pruébalo

Predice la salida

El puente Mercado – Parque está abierto, pero hay obras alrededor del Cine: Plaza – Cine y Cine – Hospital están cerradas. ¿Cuántas islas imprime el programa?

String[][] closed = {
    {"Plaza", "Cine"}, {"Cine", "Hospital"},
};
for (String[] street : closed) {
    graph.get(street[0]).remove(street[1]);
    graph.get(street[1]).remove(street[0]);
}
Map<String, Integer> islandOf = islands(graph, stops);
int count = Collections.max(islandOf.values());
System.out.println("Islas: " + count);

Respuesta

Islas: 1

Islas: 3

Islas: 2

La idea

Una pila propia en vez de recursión

Aquí las islas tienen 4 paradas cada una y la recursión baja 4 llamadas. En una ciudad en cuadrícula de 100 000 cruces, un recorrido en profundidad puede bajar decenas de miles de niveles, y cada nivel es un frame en la pila de llamadas. La pila es pequeña y se desborda. Cómo la recursión se convierte en un bucle está en la lección «De la recursión al bucle». Aquí es lo mismo: la pila pasa a ser una colección corriente.

static List<String> walk(Map<String, List<String>> graph,
                         String start) {
    List<String> order = new ArrayList<>();
    Set<String> seen = new HashSet<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        String stop = stack.pop();
        if (!seen.add(stop)) continue;
        order.add(stop);
        List<String> next = graph.get(stop);
        for (int i = next.size() - 1; i >= 0; i--) {
            if (!seen.contains(next.get(i))) stack.push(next.get(i));
        }
    }
    return order;
}

Hay dos diferencias con la recursión:

Una parada puede entrar dos veces en la pila: desde dos vecinos, antes de visitarse. Por eso la comprobación «¿ya se ha visto?» se hace también al sacarla: la segunda vez se salta.
Los vecinos entran en orden inverso. Lo último que entra sale primero, así que el primer vecino tiene que quedar arriba. De ese modo el orden es el mismo que con recursión:

Map<String, Integer> islandOf = new LinkedHashMap<>();
visit(graph, "Almacén", 1, islandOf);
System.out.println("Recursión: " + String.join(", ", islandOf.keySet()));
System.out.println("Pila propia: " + String.join(", ", walk(graph, "Almacén")));

Recursión: Almacén, Estación, Plaza, Mercado, Parque, Estadio, Hospital, Cine
Pila propia: Almacén, Estación, Plaza, Mercado, Parque, Estadio, Hospital, Cine

HashMap no conserva el orden de inserción, así que aquí la isla va en un LinkedHashMap: keySet() da las paradas en el orden en que se visitaron.

Más precisamente, para curiosos

Si metes los vecinos en el orden de la lista, el recorrido sigue siendo en profundidad y encuentra las mismas islas, solo cambia el orden de las visitas. Para las islas el orden no importa. Para los ciclos de un grafo dirigido, más abajo, sí: ahí necesitas saber cuándo termina cada parada, y con una pila de paradas eso es más difícil. Por eso findCycle es recursivo, y en grafos profundos la pila guarda un par (parada, hasta dónde ha llegado en su lista).

La idea

Un ciclo en el plan de reparto

Las reglas del plan son un grafo dirigido: la flecha Mercado → Parque significa «Mercado antes que Parque». Si las flechas forman un ciclo, no hay ningún orden que las cumpla: cada parada del ciclo tendría que ir antes que ella misma.

«Visto» por sí solo no basta para atrapar un ciclo. Mercado → Plaza lleva a una parada vista, pero no hay ciclo: de Plaza no puedes volver a Mercado. Por eso las paradas tienen tres colores:

blanco: aún no visto;
gris: en el camino actual, su llamada sigue abierta;
negro: todo lo que viene después está comprobado y no hay ciclo.

Una flecha hacia una parada gris vuelve a tu propio camino: ese es el ciclo.

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, "black");
    path.remove(path.size() - 1);
    return null;
}

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, "black");
    path.remove(path.size() - 1);
    return null;
}

Paso a paso, en palabras

Cada flecha es una regla: la parada de la que sale se entrega primero. Todas las paradas están en blanco, ninguna se ha visto. El recorrido empieza en Almacén.
Gris significa en el camino actual: Almacén → Estación → Plaza. Estas llamadas siguen abiertas.
De Plaza no sale ninguna regla: pasa a negro, todo lo que viene después está comprobado y sale del camino. Estación también está lista.
Mercado también apunta a Plaza, pero Plaza está en negro: desde ahí no hay camino de vuelta a Mercado. Dos reglas hacia la misma parada no son un ciclo.
Al otro lado del río el camino crece: Parque → Cine → Hospital → Estadio, todas en gris.
Estadio → Parque: Parque está en gris, todavía en el camino. La flecha vuelve al propio camino, y eso es un ciclo.
El ciclo es el camino desde Parque hasta el final: Parque → Cine → Hospital → Estadio → Parque. Ningún orden de estas cuatro paradas cumple todas las reglas, así que la regla Estadio → Parque tiene que desaparecer.

El bucle lanza findCycle desde cada parada blanca, como islands lanza visit:

static List<String> anyCycle(Map<String, List<String>> plan,
                             String[] stops) {
    Map<String, String> color = new HashMap<>();
    for (String stop : stops) {
        if (color.containsKey(stop)) continue;
        var found = findCycle(plan, stop, color, new ArrayList<>());
        if (found != null) return found;
    }
    return null;
}

String[][] rules = {
    {"Almacén", "Estación"}, {"Estación", "Plaza"},
    {"Almacén", "Mercado"}, {"Mercado", "Plaza"},
    {"Mercado", "Parque"}, {"Parque", "Cine"},
    {"Cine", "Hospital"}, {"Hospital", "Estadio"},
    {"Estadio", "Parque"},
};

List<String> cycle = anyCycle(plan, stops);
System.out.println(cycle == null ? "Sin ciclo" : "Ciclo: " + String.join(" → ", cycle));

Ciclo: Parque → Cine → Hospital → Estadio → Parque

Quita la última regla y el programa imprime Sin ciclo. Entonces el orden en que las paradas se ponen negras es el orden de reparto invertido. El ordenamiento topológico, la lección siguiente, se apoya en eso.

static List<String> findCycle(
        Map<String, List<String>> plan, String stop,
        Map<String, String> color, List<String> path) {
    color.put(stop, "grey");
    path.add(stop);
    for (String next : plan.get(stop)) {
        String c = color.getOrDefault(next, "white");
        if (c.equals("grey")) {
            var cycle = new ArrayList<String>(path);
            cycle.subList(0, path.indexOf(next)).clear();
            cycle.add(next);
            return cycle;
        }
        if (c.equals("white")) {
            var found = findCycle(plan, next, color, path);
            if (found != null) return found;
        }
    }
    color.put(stop, );
    path.remove(path.size() - 1);
    return null;
}

Más precisamente, para curiosos

En un grafo no dirigido cada calle es una flecha en los dos sentidos, y el vecino del que vienes siempre está «visto». Ahí hay un ciclo si llegas a una parada vista que no es aquella de la que acabas de venir. Los tres colores hacen falta para un grafo dirigido.

La idea

Cuánto cuesta

Cada parada recibe un número una vez y se visita una vez. Al visitarla mira sus calles, y una calle de doble sentido se ve desde los dos extremos. En total: V visitas y 2E miradas, O(V + E), igual que BFS.

Es lineal solo si el número de la isla es compartido por todo el recorrido. Si para cada parada preguntas «¿en qué isla estoy?» con un recorrido nuevo y un conjunto vacío de paradas vistas, haces n recorridos. Ejecuta los dos en una ciudad en cuadrícula de n cruces que el río corta en dos:

Un solo islandOf compartido para toda la ciudad O(n)
Un recorrido nuevo para cada cruce O(n²)

Algoritmo	n = 10	n = 1000	n = 2000	n = 100.000
Un solo islandOf compartido para toda la ciudad	28	4808	9730	498.100
Un recorrido nuevo para cada cruce	148	2.405.440	9.730.980	≈ 24.327.450.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 Map<String, Integer> islands(
        Map<String, List<String>> graph, String[] stops) {
    Map<String, Integer> islandOf = new HashMap<>();
    int count = 0;
    for (String stop : stops) {
        if (islandOf.containsKey(stop)) continue;
        count++;
        visit(graph, stop, count, islandOf);
    }
    return islandOf;
}

Se cuenta cada parada sacada de la pila y cada mirada a un vecino. Los dos usan su propia pila: con 100 000 cruces la recursión en el navegador se rompe con un desbordamiento de pila. Con 1000 cruces el número compartido hace 4808 operaciones, y un recorrido nuevo para cada cruce, 2 405 440. Con 2000 el recorrido nuevo ya está en 9 730 980, mientras que el compartido con 100 000 hace 498 100.

Pruébalo

Encuentra el error

Un compañero decidió que en visit la isla debe crecer con cada paso. El programa imprime:

static void visit(Map<String, List<String>> graph,
                  String stop, int island,
                  Map<String, Integer> islandOf) {
    islandOf.put(stop, island);
    for (String next : graph.get(stop)) {
        if (!islandOf.containsKey(next)) {
            visit(graph, next, island + 1, islandOf);
        }
    }
}

Islas: 5
Isla 1: Almacén
Isla 2: Estación, Parque
Isla 3: Plaza, Estadio
Isla 4: Mercado, Hospital
Isla 5: Cine

Hay cinco islas, y Estación y Parque están «en una isla», aunque los puentes están cerrados. ¿En qué línea está el error?

Elige la línea con el error.

Más precisamente

Hasta qué profundidad puede llegar la recursión

La pila de un hilo en Java es por defecto de aproximadamente 1 MB (se ajusta con -Xss), lo que alcanza para unos miles o decenas de miles de llamadas a visit. Un desbordamiento lanza StackOverflowError. Puedes capturarlo, pero el recorrido ya está roto. Para grafos grandes usa ArrayDeque como pila: push y pop.

Ejercicio

Las calles críticas

Resuélvelo en tu editor.

Calles críticas. El puente Mercado – Parque está cerrado por un mes, y Plaza – Cine sigue funcionando. Una calle es crítica si cerrarla parte la ciudad en más islas. Cierra el puente, imprime cuántas islas hay, luego para cada calle abierta quítala, cuenta las islas con islands y vuelve a ponerla. Imprime las calles críticas en el orden de streets.

String[][] closed = {
    {"Mercado", "Parque"},
};

Islas: 1
Críticas: Plaza - Cine, Cine - Hospital, Parque - Estadio, Hospital - Estadio

Más tareas

La isla más grande. Imprime la isla con más paradas y cuántas horas de furgoneta a la semana necesita si cada parada lleva 3 horas.
El ciclo en el plan. Escribe findCycle con tu propia pila: pon en la pila un par (parada, índice del siguiente vecino), y la parada se pone negra cuando el índice llega al final de su lista.
Islas en el mapa. El mapa del almacén es una cuadrícula de # (estante) y . (libre). Cuenta las zonas libres, donde los vecinos de una celda son arriba, abajo, izquierda y derecha.

Test

Ponte a prueba

1. ¿Qué hace DFS cuando todo alrededor de la parada actual ya se ha visto?Vuelve a la parada de la que vino y prueba el siguiente vecino de esa paradaDetiene todo el recorridoEmpieza de nuevo desde el almacén

2. ¿Por qué islands recorre todas las paradas en vez de lanzar visit solo desde el almacén?Porque el orden de las paradas importa para DFSPara comprobar que visit funciona bienUn visit solo alcanza su propia isla; las paradas al otro lado de los puentes cerrados se quedan sin número

3. En el plan dirigido findCycle ve una flecha hacia una parada negra. ¿Es un ciclo?Sí: la parada ya se ha vistoNo: la parada negra está totalmente comprobada y desde ella no hay camino de vuelta a la actualDepende del orden de las reglas

4. La ciudad tiene 100 000 cruces en una cadena larga. ¿Qué le pasa al visit recursivo?Funciona, pero es O(V²)Nada: la recursión es rápidaLa profundidad llega a 100 000 llamadas y la pila se desborda; necesitas una pila propia

DFS: islas y ciclos

Cookies