← Volver a los ejercicios

profundidades: el nivel en el árbol de la búsqueda

La búsqueda en profundidad no solo dice a quién alcanza: también deja, en cada vértice, a qué distancia quedó por el camino que ella tomó. Ese número no es la distancia más corta, y ver dónde se separan las dos es todo el ejercicio.

1. La especificación y la predicción

Entrada: un grafo G en lista de adyacencia y un vértice s.  Salida: una lista p donde p[v] es el número de aristas del camino que la búsqueda recorrió desde s hasta v, y -1 si no llegó.

Grafo y arranque:
¿Cuál es el nivel más alto que alcanza la búsqueda?

2. Ejecute y mire bajar la búsqueda

Azul: ya visitado. En naranja, junto a cada vértice, su nivel.

Pila de llamadas: –
Paso 0 de 0
La pila crece cuando la línea 7 baja a un vecino nuevo y se encoge cuando una llamada se queda sin vecinos por mirar.

3. Una fila por llamada

LlamadaVérticeNivelPila en ese momento

4. Qué cuenta ese número

¿Qué es p[v]?
Nivel contra distancia
VérticeNivel en el árbolDistancia mínima
Acierte la pregunta de arriba y lleve la ejecución hasta el final.
Las filas resaltadas son los vértices donde la búsqueda en profundidad llegó dando un rodeo.

5. Una pregunta más

Si los vecinos de cada vértice estuvieran guardados en orden decreciente, ¿qué cambia?
La línea 5 recorre G[u] en el orden en que esté guardado, y la línea 7 baja por el primero que encuentre sin visitar. Cambiar ese orden cambia por dónde baja la búsqueda, y con ello los niveles. Lo que no cambia es a quién alcanza: eso solo depende de qué caminos existen.

6. Para llevarse

Sin solución aquí. Modifique visitar para que además construya la lista padre, donde padre[v] es el vértice desde el cual la búsqueda bajó a v. Después responda: ¿cómo se reconstruye con ella el camino de s a un vértice cualquiera, y por qué ese camino tiene exactamente p[v] aristas?