Saltar a contenido

Clase 7. Grafos implícitos

Viernes 18 de septiembre de 2026.

Un grafo cuyos vértices y aristas nadie guarda: hay una regla que dice qué es un vértice y otra que produce los vecinos, y el recorrido llama a esa regla cuando la necesita. La cuadrícula de Jaimico y el café es el primer ejemplo, y de ahí se pasa a tres problemas de juez en línea: un bosque con zonas peligrosas, la ruta con menos saltos en una red, y el componente más grande de un imperio.

  • Grafos implícitos


    El costo de los recorridos, Jaimico y el café con las dos versiones del DFS y la amplitud, y los tres problemas con el método completo: entrada, salida, grafo, algoritmo, código y costo.

    Entrar

  • Diapositivas


    Las 67 láminas con las anotaciones de la sesión y dos páginas de tablero con los casos de la muestra de Poor Trade Advisor.

    Abrir

Ejercicios

Seis interactivos, en el orden de la sesión: la amplitud sobre un laberinto nuevo, el bosque donde el peligro se marca a mano antes de recorrer, la ruta con predecesores en una red dirigida, los componentes pintados de colores, tres fallas para encontrar, y la cuadrícula donde marcar la celda falla y marcar el estado acierta. Después, siete en papel y cinco para programar.

Todos están en la página de ejercicios.

Antes de entrar

Conviene tener a mano los recorridos y su costo, que son la base de todo lo que sigue.