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.
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ó.
Azul: ya visitado. En naranja, junto a cada vértice, su nivel.
| Llamada | Vértice | Nivel | Pila en ese momento |
|---|
p[v]?| Vértice | Nivel en el árbol | Distancia mínima | |
|---|---|---|---|
| Acierte la pregunta de arriba y lleve la ejecución hasta el final. | |||
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.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?