← Volver a los ejercicios

Quince páginas y sus enlaces

El último y el más exigente, para cuando los anteriores ya salen solos. Quince páginas de un sitio y veintitrés enlaces: demasiado para seguir la traza de memoria, que es el tamaño en que estos algoritmos dejan de ser un ejercicio de papel. Dos páginas están en el mismo bloque cuando se puede ir y volver entre ellas siguiendo enlaces.

1. El sitio

Veintitrés enlaces: 0 → 1, 1 → 2, 2 → 3, 3 → 0, 4 → 5, 5 → 4, 6 → 7, 7 → 8, 8 → 6, 10 → 11, 11 → 10, 13 → 14, 14 → 13, 1 → 4, 2 → 6, 5 → 6, 5 → 9, 7 → 9, 8 → 10, 9 → 12, 11 → 12, 12 → 13, 10 → 14.

¿Cuántos bloques de páginas mutuamente alcanzables hay?

2. La segunda pasada, llamada por llamada

La lista es ord, ya calculada por la primera búsqueda en profundidad y leída de izquierda a derecha. Cada llamada que encuentra su página sin asignar pinta un bloque entero; las demás se devuelven sin hacer nada y quedan tachadas.

Llamadas ejecutadas: 0 de 15

BloqueArranca enPáginasTamaño

3. El mapa de bloques

¿Cuántas aristas tiene el grafo de componentes?

4. El mismo sitio sin las direcciones

Borre las puntas de los enlaces y quedan veinte aristas sin dirección. Dos preguntas sobre ese grafo.

Componentes conexos y puntos de articulación del sitio sin direcciones:

5. Un enlace de más

El administrador agrega un enlace de vuelta desde la página 14 hasta la portada, 14 → 0.

¿Cuántos bloques quedan entonces?

6. Para llevarse

Sin solución aquí. Tres preguntas sobre el mismo sitio.