Grafos dirigidos
Los 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 make
Un 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 profundidad
En 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:
AFEDBGJKLMCHI
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 transitivo
El 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:
A
B
C
D
E
F
G
H
I
J
K
L
M
A
1
0
1
0
0
0
0
0
0
0
0
0
0
B
1
1
0
0
0
0
0
0
0
0
0
0
0
C
0
0
1
0
0
0
1
0
0
0
0
0
0
D
0
0
0
1
1
0
0
0
0
0
0
0
0
E
0
0
0
0
1
1
1
0
0
0
0
0
0
F
1
0
0
1
0
1
0
0
0
0
0
0
0
G
1
0
0
0
0
0
1
1
0
0
0
1
0
H
0
0
0
0
0
0
0
1
1
0
0
0
0
I
0
0
0
0
0
0
0
1
1
0
0
0
0
J
0
0
0
0
0
0
1
0
0
1
0
0
0
K
0
0
0
0
0
0
0
0
0
1
1
0
0
L
0
0
0
0
0
0
0
0
0
1
0
1
1
M
0
0
0
0
0
0
0
0
0
1
0
1
1
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 <= V; y++)
for (x = 1; x <= V; x++)
if (a[x][y])
for (j = 1; j <= V; j++)
if (a[y][j]) a[x][j] = 1;
El algoritmo de Warshall se basa en la afirmacin de que si es posible llegar del nodo
X al nodo Y, y del nodo Y al nodo J, entonces existe un camino del nodo X al nodo J.
De hecho, para poder completar el cierre transitivo del grafo en una sola pasada usa la
afirmacin de que si existe un camino de X a Y usando nodos con ndices menores a
Y, y existe una forma de llegar de Y a J, entonces hay un camino de X a J usando
nodos con ndices menores a Y+1.
Luego de ejecutar este algoritmo sobre nuestro grafo, obtenemos:
A
B
A
1
0
B
1
1
C
1
0
D
1
0
E
1
0
F
1
0
G
1
0
H
0
0
I
0
0
J
1
0
K
1
0
L
1
0
M
1
0
C
D
E
F
G
H
I
J
K
L
M
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
Fijndonos en el grafo, vemos que para cada fila aparece todos los nodos a los que
puedo llegar desde la misma. Como vimos en la bsqueda primero en profundidad, los
nodos H e I no pueden ser accedidos desde el resto del grafo, lo que se puede ver en
la matriz de cierre transitivo. A su vez, desde H o I puedo acceder al resto del grafo, lo
que tambin pude observarse en la matriz.
Vemos que el algoritmo contiene 3 bucles anidados, es claramente de tipo O(n 3),
siendo n = V, la cantidad de nodos del grafo.
Tambin existe, como puede suponerse, una versin recursiva de este algoritmo, que
es de tipo O(n2), pero es de implementacin ms complicada (aparte de por ser
recursiva, consumir ms memoria).
Camino ms corto
En algunos casos puede ser necesario no solo ver si existe un camino entre dos
nodos, sino calcular el ms corto entre ellos. Para lograr esto puede usarse el
siguiente algoritmo:
for (y = 1; y <= V; y++)
for (x = 1; x <= V; x++)
if (a[x][y])
for (j = 1; j <= V; j++)
if (a[x][j] > 0)
if(!a[x][j] || (a[x][y] + a[y][j] < a[x][j]))
a[x][j] = a[x][y] + a[y][j];
Como se puede ver este algoritmo (inventado por R. W. Floyd) es muy similar al de
Warshall. La lgica que sigue es esencialmente la misma, estando la diferencia en la
6 lnea. En ese if, si no existe una arista entre X y J o si la arista que existe es mayor
a la suma de XY ms YJ, le asigna la que corresponde a XY ms YJ. Es decir, siempre
se queda con la menor posible.
De forma similar al algoritmo de Warshall, este es de tipo O(n3).
Orden Topolgico
El orden topolgico es el mismo que fue definido en clase. Como puede suponerse,
el orden puede solo ser determinado en un grafo dirigido acclico, o DAG (Directed
Acyclic Graph). De esta forma, se puede observar un orden parcial entre nodos,
ordenndolos de forma tal que ningn nodo es visitado antes que los nodos que
apuntan a el. Si por ejemplo, el grafo representa los diferentes pasos en un proceso,
ningn paso es ejecutado antes de los que le preceden.
En algunas aplicaciones puede ser necesario usar un orden topolgico inverso. En
este caso se tienen dos posibilidades:
Recorrer el grafo en orden y almacenar los nodos en una pila, para luego
sacarlos en el orden topolgico inverso.
Recorrer el grafo primero en profundidad, pero marcando los nodos como
visitados al final del algoritmo, y no al principio.
Componentes fuertemente conectados
Como vimos en el recorrido primero en profundidad, puede ser que desde un nodo
dado no pueda acceder a todo el resto del grafo. Esto (ms otras condiciones)
ocasiona que los nodos puedan ser divididos en componentes fuertemente
conectados. Todos los nodos de un mismo componente fuertemente conectado son
accesibles entre si, pero no es posible salir del componente y volver a entrar. En el
caso del grafo de ejemplo, los componentes fuertemente conectados seran (pueden
comprobarlo ustedes):
HI
DEF
ACGJLM
Existe un algoritmo para encontrar componentes fuertemente conectados, desarrollado
por R. E. Tarjan, en 1972. Es similar al usado para buscar componentes biconexos.
