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?