Grafos dirigidos

Grafos dirigidosLos grafos dirigidos son grafos en los que las aristas tienen una direccin definida; por ejemplo, se puede dar el caso de poder ir del nodo A al nodo B, pero no al revs. En la mayora de los casos la direccin de las aristas indica algn tipo de relacin de precedencia entre los nodos. Los grafos dirigidos pueden ser usados para:

Modelar lneas de fabricacin, en las que diferentes procesos dependen de otros Manejar dependencias en la compilacin de archivos, como hace el makeUn ejemplo de grafo dirigido podra ser:

Podemos ver claramente que por ejemplo, existe una arista de A a G, pero no de G a A. Sin embargo, est permitido que halla dos aristas de direcciones distintas entre los mismos nodos, como por ejemplo entre H e I, y entre L y M.Bsqueda primero en profundidadEn el caso de grafos dirigidos, la bsqueda primero en profundidad es casi igual a la similar en el caso de grafos no dirigidos.En ejemplo en pseudo-cdigo sera:

Recorrer (grafo G) {

marcar_visitado(todos F);

for (todos vrtices V de G)

DFS (G ( V);

}

DFS (vrtice V) {

visitar(V);

marcar_visitado(V);

for ( ; v ; v = SgteAdy)

if (!visitado(V))

DFS(V);

}

Aplicando este algoritmo al grafo anterior podemos visitar los nodos en el orden:A F E D B G J K L M C H I

Este orden no es el nico posible, podra haber empezado por otro nodo, o haber seguido otro orden entre los adyacentes.

Notamos tambin que pese a que el H e I estn conectados al grfico, no pueden ser accedidos desde A; es necesario cambiar de nodo, y empezar a recorrerlo de nuevo. Es decir, en vez de representarse el recorrido como un rbol, se representa como un bosque. Si se hubiera empezado a recorrer el grafo por H, podra haber recorrido todos los nodos dentro del mismo rbol de recorrido, puesto que desde H puedo acceder a cualquier nodo.

Cierre transitivoEl clculo de cierre transitivo permite saber si existe un camino de longitud mayor o igual a 1 entre dos nodos dados. Es decir, indica que nodos estn de alguna forma conectados.Para esto es til trabajar con la matriz de adyacencias, colocando un 1 en los nodos que estn conectados, y un 0 en los que no lo estn. De esta forma, para este grafo la matriz quedara:ABCDEFGHIJKLM

A1100011000000

B0100000000000

C1010000000000

D0001010000000

E0001100000000

F0000110000000

G0010101001000

H0000001110000

I0000000110000

J0000000001111

K0000000000100

L0000001000011

M0000000000011

Si sobre esta matriz se ejecuta el siguiente algoritmo (inventado por S. Warshall en 1962), se obtiene la matriz de adyacencias que corresponde al clculo del cierre transitivo para todo par de nodos X e Y:for (y = 1; y