← Volver a los ejercicios

mas_lejano: hasta dónde llega el grafo

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

TurnoSaleEncolaCola 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.