Se realiza una búsqueda primero en profundidad en un gráfico acíclico dirigido. Sea d[u] el momento en que se visita el vértice u por primera vez y f[u] el momento en que termina la llamada dfs al vértice u. ¿Cuál de las siguientes afirmaciones es siempre verdadera para todos los bordes (u, v) en el gráfico?
(A) d[u] < d[v]
(B) d[u] < f[v]
(C) f[u] < f[v]
(D) f[u] > f[v]
Respuesta: (D)
Explicación: 
Iniciando DFS en el Node V
1] Visita(V) -> DFS(X) ->Visita(X) ->DFS(U) ->Visita(U) -> retroceso(X) -> retroceso( V)
Por lo tanto: d[U] > d[V], d[U] < f[V], f[U] < f[V]
Pero, el orden de visita es justo lo opuesto al orden de llegada.
Por lo tanto f[U] >
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA