← Volver a los ejercicios

La marca de visitados

Un grafo no se recorre como una lista: se puede volver por donde uno vino. Aquí está el mismo recorrido con la marca y sin ella, y el contador de vueltas dice de un vistazo qué pasa cuando falta.

1. Los tres montajes

El parámetro marcar enciende y apaga la marca. El limite es un tope de vueltas: sin él, la primera corrida no terminaría nunca y la página se quedaría colgada.

Montaje:
¿Cuántas vueltas da el while?

2. Ejecute

Pila: vacía
Anotados: –
Paso 0 de 0
Compare las dos primeras corridas mirando el contador distintos contra el de vueltas.

3. Qué hace terminar al recorrido

4. Y aun con la marca, falta algo

En H3 el recorrido con marca termina, pero deja un vértice sin visitar. ¿Qué hace falta?
Desde el 0 se llega a seis de los siete vértices: al 6 no entra ninguna arista. El ciclo externo recorre los vértices de 0 a n−1 y arranca un recorrido nuevo en cada uno que siga sin marcar, de modo que ninguno queda por fuera sin importar cómo esté repartido el grafo.

5. Para llevarse

Sin solución aquí. En la versión con marca, un mismo vértice puede entrar varias veces a la pila antes de que le llegue el turno, y la línea 8 lo descarta al salir. Escriba una versión que no permita duplicados en la pila y responda: ¿cuántas entradas puede tener la pila como máximo en cada una de las dos versiones, en términos de $V$ y $E$? ¿Cambia el orden de visita?