Necesitas las representaciones de grafos de la sección 11 y los contratos de pila y cola de las secciones 5 y 6.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar DFS con BFS y resolver un caso nuevo.
Reserva entre 75 y 120 minutos o divide el laboratorio en dos sesiones.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan DFS y BFS? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Cerrarás la ruta usando las estructuras anteriores para recorrer redes y entregar una biblioteca Java que pueda comprobarse y explicarse.
Al terminar podrás
- DFS avanza por una rama y recuerda cómo regresar
- BFS descubre por capas y obtiene distancias mínimas sin peso
- El proyecto final combina contratos, pruebas y mediciones
01
Profundidad
DFS avanza por una rama y recuerda cómo regresar
DFS marca el vértice al descubrirlo y visita sus vecinos no marcados. Puede implementarse con recursión o una pila explícita; esta última evita agotar la pila de llamadas en grafos muy profundos. En un grafo no dirigido permite encontrar componentes conexas; en uno dirigido, la conectividad fuerte requiere un algoritmo específico.
Marca antes de explorar vecinos.
En un grafo no dirigido, inicia desde cada vértice no visitado para cubrir sus componentes.
Con listas de adyacencia, el recorrido completo cuesta O(V + E).
¿Qué fallo evita el conjunto de visitados?
Mostrar respuesta ＋
Evita volver indefinidamente por ciclos y procesar muchas veces el mismo vértice.
02
Amplitud
BFS descubre por capas y obtiene distancias mínimas sin peso
BFS marca el origen, lo agrega a una cola y procesa sus vecinos. La primera vez que descubre un vértice obtiene la mínima cantidad de aristas desde el origen en un grafo sin pesos. Un mapa de predecesores permite reconstruir el camino; con listas de adyacencia, el recorrido cuesta O(V + E).
La cola conserva las capas.
Marca al encolar, no al retirar.
Con pesos distintos se necesita otro algoritmo.
¿Por qué se marca al vecino cuando se encola?
Mostrar respuesta ＋
Para impedir que varios padres lo encolen repetidamente antes de que llegue su turno.
03
Entrega verificable
El proyecto final combina contratos, pruebas y mediciones
La biblioteca final incluye interfaces pequeñas, implementaciones encapsuladas y pruebas para vacío, un elemento, muchos, duplicados y errores. Cada estructura documenta invariantes y complejidad. La aplicación de rutas define un formato de archivo simple —por ejemplo, una arista origen,destino por línea—, valida cada registro y usa DFS y BFS sin depender de detalles internos.
Prueba propiedades además de ejemplos.
Compara tu resultado con java.util cuando exista equivalente.
Mide después de demostrar corrección.
¿Qué evidencia demuestra que la implementación está lista?
Mostrar respuesta ＋
Contratos claros, invariantes preservados, pruebas normales y frontera, comparación con resultados conocidos y una medición reproducible de las operaciones clave.
Tu recorrido en tres ideas
- DFS avanza por una rama y recuerda cómo regresar
- BFS descubre por capas y obtiene distancias mínimas sin peso
- El proyecto final combina contratos, pruebas y mediciones
Entrega un explorador de rutas
Integra modelado, listas de adyacencia, pila, cola, visitados, predecesores, archivos y pruebas.
CASO
Una comunidad necesita cargar lugares y conexiones bidireccionales sin peso, identificar grupos aislados y encontrar rutas con menos tramos.
Procedimiento
- Define formato, validaciones y semántica del grafo no dirigido antes de cargar.
- Implementa componentes conexas con DFS y camino mínimo en aristas con BFS y predecesores.
- Prueba ciclos, aislamiento, origen igual a destino y ruta inexistente.
Evidencia mínima
- Archivo de ejemplo y errores comprensibles.
- Orden de visita y conjunto de componentes.
- Camino reconstruido y comparación con casos conocidos.
Mostrar razonamiento modelo ＋
DFS recorre cada componente; BFS desde el origen asigna un predecesor al descubrir y reconstruye desde destino. La ausencia de camino es un resultado válido, no una excepción inesperada.
Para ir más lejos¿Qué algoritmo necesitarías si cada conexión tuviera un tiempo distinto?
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Marcar un vértice demasiado tarde y encolarlo muchas veces.
Afirmar que BFS encuentra el camino de menor costo cuando hay pesos distintos.
Ahora hazlo sin guía
Entrega una aplicación para un grafo no dirigido y sin pesos que cargue un archivo, muestre componentes conexas con DFS y reconstruya un camino mínimo en cantidad de aristas con BFS.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Maneja grafos desconectados y ciclos.
- Conserva predecesores para reconstruir.
- Incluye pruebas, invariantes y mediciones reproducibles.