Indagamos por diferentes espacios para así traerte la solución a tu dilema, si tienes preguntas puedes dejar un comentario y respondemos porque estamos para ayudarte.
Solución:
Ambos algoritmos están bien. El segundo es una traducción directa de recursivo a basado en pila. Todos los estados de mutación se almacenan en la pila. G nunca cambia durante la ejecución del algoritmo.
Los algoritmos producirán un árbol de expansión para cada región desconectada, según el orden en que el algoritmo visitó cada nodo. Los árboles se representarán con referencias a los nodos principales (u.π) y como árboles de segmentos (u.d y u.f).
Un hijo tendrá una referencia a su nodo padre (o NULL si es raíz), además de tener su rango (child.d .. child.f) contenido dentro del rango de su padre.
parent.d < child.d < child.f < parent.f
child.π = parent
Editar: Encontré un error en la traducción. En realidad, no está empujando el estado actual a la pila, sino un argumento de método futuro. Además, no está coloreando los nodos reventados GRAY y estableciendo el f campo.
Aquí hay una reescritura del primer algoritmo original:
algorithm Stack-DFS(G)
for each vertex u ∈ G.V
u.color ← WHITE
u.π ← NIL
time ← 0
S ← empty stack
for each vertex u ∈ G.V
if u.color = WHITE
# Start of DFS-VISIT
step ← 1
index ← 0
loop unconditionally
if step = 1
# Before the loop
u.color ← GRAY
time ← time + 1
u.d ← time
step ← 2
if step = 2
# Start/continue looping
for each vertex v ∈ G.Adj[u]
i ← index of v
if i ≥ index and v.color = WHITE
v.π ← u
# Push current state
push((u, 2, i + 1), S)
# Update variables for new call
u = v
step ← 1
index ← 0
# Make the call
jump to start of unconditional loop
# No more adjacent white nodes
step ← 3
if step = 3
# After the loop
u.color ← BLACK
time ← time + 1
u.right ← time
# Return
if S is empty
break unconditional loop
else
u, step, index ← pop(S)
Probablemente haya algunos lugares que podrían optimizarse, pero al menos deberían funcionar ahora.
Resultado:
Name d f π
q 1 16 NULL
s 2 7 q
v 3 6 s
w 4 5 v
t 8 15 q
x 9 12 t
z 10 11 x
y 13 14 t
r 17 20 NULL
u 18 19 r
Te mostramos las comentarios y valoraciones de los lectores
Si te sientes incitado, eres capaz de dejar una crónica acerca de qué te ha parecido esta división.