Un recorrido por capas contesta más de lo que parece. Aquí
se usa para encontrar el vértice más apartado del arranque, y de paso se ve
por qué la primera vez que la búsqueda toca a alguien es siempre por el
camino más corto.
1. La especificación y la predicción
Entrada: un grafo G en lista de
adyacencia y un vértice s. Salida: el vértice
alcanzable más lejano de s y su distancia en número de
aristas.
Grafo y arranque:
¿A qué distancia está el más lejano?
2. Ejecute y mire las capas
Un color por capa;
el borde negro marca el vértice que salió de la cola.
Cola: vacía
Paso 0 de 0
La cola entrega por el frente y recibe por atrás.
Mire qué capas conviven en ella en cada momento.
3. Una fila por vértice que sale
Turno
Sale
Encola
Cola después
4. Qué hay dentro de la cola
En cualquier momento, los vértices que
están en la cola…
5. Dónde se fija la distancia
¿En qué momento queda fijada d[v]?
Un vértice puede tener varios vecinos que quieran
encolarlo. El que llega primero le pone la distancia y la condición de la
línea 11 impide que los demás la toquen. Como los vértices salen por
capas, ese primero está en la capa más baja posible, y por eso
d[v] queda con el número mínimo de aristas.
6. Para llevarse
Sin solución aquí. La excentricidad de un
vértice es la distancia a su vértice más lejano, que es justo lo que
devuelve este programa. El diámetro del grafo es la mayor
excentricidad de todos sus vértices, y el radio, la menor. Escriba
los dos usando mas_lejano, diga cuánto cuestan en términos de
$V$ y $E$, y responda qué pasa con ambos cuando el grafo no es conexo.