Dfs Recursividad

DEPTH-FIRST SEARCH

Es un método de exploración de grafos (orientados o no). Parte desde un vértice llamado fuente, explorando recursivamente sus sucesores. Busca en profundidad tanto como esposible, cada arco es explorado desde el último vértice descubierto v, cuando todos los arcos desde v han sido explorados, la búsqueda retrocede (“backtracks”) para explorar los arcos, comenzando desde elvértice desde el cual v fue descubierto.
El proceso continúa hasta que todos lo vértices alcanzables desde el vértice fuente original han sido descubiertos. Si restan vértices sin descubrir, uno deellos es seleccionado como nuevo vértice fuente y la búsqueda se repite.
DFS Forest aplicado a un grafo G= (V,A) retorna un bosque de exploración depth-first compuesto de uno o más árboles deexploración depth-first.

DFS_forest (G)
{
for cada vértice u ( V
{
Marca[u]= NO_VISITADO;
Padre[u]= NULO;
}
for cada vértice u ( V
if Marca[u]= NO_VISITADO
DFS (G, u);
}

DFS (G, u)
{Marca[u]= VISITADO;
for cada vértice v ( Adyacente[u]
if Marca[v]= NO_VISITADO
{
Padre[v]= u;
DFS (G,v);
}
}

El tiempo de ejecución del algoritmo DFS Forest es O(m), donde m esel máximo entre el número de vértices y el número de arcos.


SORT TOPOLÓGICO


Sort Topológico de un Grafo Acíclico Dirigido (DAG) G= (V,A) es un orden lineal de todos los vértices tales que siG contiene un arco (u,v) , luego u aparece antes de v en el ordenamiento (si el grafo es no acíclico el orden lineal no es posible). Los DAG son generalmente usados en muchas aplicaciones paraindicar la precedencia de eventos, el ordenamiento topológico devuelve una posible secuencia válida en la que deben realizarse dichos eventos.
Para obtener el orden topológico de un grafo G:
1. Se realizaun dfs forest, marcando cada vértice con el número en post-orden (Una vez que se han explorado todos los vértices a partir de un vértice dado, este es marcado con un número antes de retroceder en...