Download Algoritmos sobre Grafos

Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Algoritmos sobre Grafos
Hugo Franco, PhD
21 de febrero de 2011
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Contenido
1
Deniciones
2
Algoritmos básicos de búsqueda
3
Algoritmos de ruta más corta
4
Algoritmos basados en árboles
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Deniciones sobre Grafos
Par de una lista de nodos y una lista de enlaces, denidos a su vez
como pares del conjunto de nodos.
G ≡
{V, E}
V
≡
{v1 , v2 , . . . , vn }
E
≡
{. . . , {vi , vj }, . . . } , i, j ∈ [1, n], i 6= j
Si el orden de los elementos
vi
enlace es relevante, se tiene un
y
vj
en cada par del conjunto de
grafo dirigido
Representaciones en algoritmos:
Lista de Adyacencia:
el nodo
ain ,
cada
ai
es la lista de nodos enlazados con
i−ésimo
A ≡ aij m×n , aij = 1 sí y sólo sí vi está
0 en caso contrario. Se puede extender asignando
Matriz de Adyacencia:
conectado con
vj ,
aij un valor asociado a la intensidad del enlace (matriz de
proximidad) o la propia distancia geodésica de un nodo a otro
(matriz geodésica)
a los
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Ciclo, Grafos Acíclicos
Ciclo: secuencia de enlaces adyacentes en
un grafo, recorridos sin repetir enlaces y
cuyo nodo de partida es el mismo nodo de
llegada.
Ciclo Hamiltoniano: aquel que recorre
todos sus nodos exactamente una vez
(excepto el de partida/llegada).
Ciclo Euleriano: ciclo que contiene todos
los enlaces de un grafo, cada uno de ellos
una única vez.
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Grafo Dirigido Acíclico
Grafo dirigido que no tiene ciclos
para cada nodo, no hay un camino directo que
empiece y termine en éste.
Fuente: nodo sin enlaces de entrada,
Sumidero: nodo sin enlaces de salida.
Un GDA (DAG) nito tiene por lo menos una
fuente y un sumidero.
La profundidad de un nodo es la longitud del
camino más largo desde una fuente a éste
La altura de un nodo es la mayor longitud del
camino más largo entre éste y un sumidero.
La longitud de un DAG nito es la longitud
(número de arcos) del camino más largo.
máxima altura de todas las fuentes, máxima
profundidad de todos los sumideros.
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Etiquetado
Los recorridos sobre grafos exigen usualmente almacenar de forma
accesible el Estado de cada nodo (y en ocasiones, enlace) del grafo
según haya sido recorrido / analizado durante el proceso de análisis
/ búsqueda
La forma de almacenar ese estado se puede implementar a través de
atributos asignados a los nodos que representen el estado en el que
se encuentra el nodo con un valor asociado a cada estado,
El estado de un nodo puede constar de uno o más parámetros,
simbólicos o numéricos. En casos de representaciones simbólicas, se
suelen emplear enumeraciones descriptivas, que determinan la
implementación de las reglas de evolución de los nodos del grafo
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Etiquetado
Los recorridos sobre grafos exigen usualmente almacenar de forma
accesible el Estado de cada nodo (y en ocasiones, enlace) del grafo
según haya sido recorrido / analizado durante el proceso de análisis
/ búsqueda
La forma de almacenar ese estado se puede implementar a través de
atributos asignados a los nodos que representen el estado en el que
se encuentra el nodo con un valor asociado a cada estado,
El estado de un nodo puede constar de uno o más parámetros,
simbólicos o numéricos. En casos de representaciones simbólicas, se
suelen emplear enumeraciones descriptivas, que determinan la
implementación de las reglas de evolución de los nodos del grafo
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Etiquetado
Los recorridos sobre grafos exigen usualmente almacenar de forma
accesible el Estado de cada nodo (y en ocasiones, enlace) del grafo
según haya sido recorrido / analizado durante el proceso de análisis
/ búsqueda
La forma de almacenar ese estado se puede implementar a través de
atributos asignados a los nodos que representen el estado en el que
se encuentra el nodo con un valor asociado a cada estado,
El estado de un nodo puede constar de uno o más parámetros,
simbólicos o numéricos. En casos de representaciones simbólicas, se
suelen emplear enumeraciones descriptivas, que determinan la
implementación de las reglas de evolución de los nodos del grafo
Hugo Franco, PhD
Algoritmos sobre Grafos
Algoritmos Básicos de Búsqueda
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Problema del Ordenamiento Topológico
Dado un Grafo Dirigido Acíclico, el problema del ordenamiento
topológico consiste en
Encontrar un ordenamiento de los vértices tal que todos ellos se listen
hacia adelante (nodo inicial, nodo nal) de acuerdo a sus enlaces
Utilidad: Asignar una prioridad a una lista de tareas con restricciones
de precedencia (hacer primero la tarea A porque una tarea B
depende del resultado de A, etc...)
Se asume que el grafo está representado como una lista de
adyacencias
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Búsqueda en Profundidad
Dada una lista de vértices
Para
i=1
Si
vi
hasta
V
y una lista de enlaces
E,
hacer
n
no está marcado como visitado,
RecorrerProfundidad(i)
Fin
Función RecorrerProfundidad(índice
Marcar
vi
Agregar
i
a la lista de recorrido
Usando la lista de enlaces
Si
vj
i)
como visitado
e,
para cada vecino
vj
de
vi
no está marcado como visitado
RecorrerProfundidad(j )
Agregar el enlace que une a
vi con vj al árbol de recorrido
Regresar
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Búsqueda en Anchura
Dada una lista de vértices
cola de prioridad
Q,
Marcar el nodo inicial
Añadir
i
encolar
vi
Mientras
V
y una lista de enlaces
E,
deniendo una
hacer
vi
como visitado
a la lista de recorrido
en
Q
Q 6= Ø
extraer
ui
desde
Para cada vecino
Si
Q
uj
de
ui
uj no esta marcado como visitado
agregar uj a Q
marcar uj como visitado
Agregar el enlace que une a ui con uj al árbol de recorrido
Hugo Franco, PhD
Algoritmos sobre Grafos
Algoritmos de Ruta más corta
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Algoritmo de BellmanFord
Algoritmo de programación dinámica
Encontrar la ruta más corta desde todos los nodos a un nodo sumidero
t.
Se
suele calcular las longitudes de los caminos más cortos así que posteriormente
se pueden reconstruir las rutas fácilmente. La idea de algoritmo es
1
Para cada nodo
v,
encontrar la longitud de la ruta más corta a
al menos una arista o etiquetar
2
Supóngase para todo
t
que usa
i−1
v
∞
xj
hasta
t
que usa
se tienen las longitudes de la ruta más corta hasta
o menos enlaces. La ruta más corta desde
o menos enlaces primero irá a algún vecino
corta desde
t
si no hay tal ruta.
que usa
i−1
xj
de
v
v
a
t
que usa
y tomar la ruta más
o menos enlaces (paso 1). Así, se
necesita tomar únicamente los mínimos de la distancia entre todos los
vecinos
3
xj
de
v
Repetir mientras
i≤n−1
Hugo Franco, PhD
Algoritmos sobre Grafos
i
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Pseudocódigo BellmanFord
1
Inicializar d[v][0] =
2
Para
1
i=1
Para cada
1
3
hasta
v,
for
v 6= t.
d[t][i]=0
∀
i.
n−1
v 6= t
d[v][i] =
Para cada
∞
min
(v,xj )∈E
(len(v,x) + d[x][i-1])
escribir d[v][n-1].
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Todas las distancias mínimas: FloydWarshall
Sea A[i][j] la matriz de proximidad del grafo
En vez de incrementar el número de enlaces en la ruta, se recorrerá
el grafo por vértices
Se incrementará el contador sobre el conjunto de vértices que se
admiten como intermedios en la ruta estimada
Usando la matriz de i, después de cada iteración del bucle exterior,
A[i][j] será igual a la longitud del camino más corto de
puede usar los vértices en la secuencia
Para
k
= 1 hasta
Para cada
vi
a
vj
que
{1, 2, . . . , k}:
n
i, j
A[i][j] = min( A[i][j], (A[i][k] + A[k][j]); .
Aunque el algoritmo tarda del orden de
n3 ,
donde n es el número de
nodos, el código es simple y compacto.
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Todas las distancias mínimas: Dijkstra
Sea un grafo dirigido
conectado de N
nodos, sea
x
el nodo origen y
un vector (array) de distancias a los diferentes nodos indexados por
1
Inicializar el array de todas las distancias en
Dn
con un valor innito
relativo (valor inicial desconocido), exceptuando la de
colocar en 0 (la distancia de
2
Sea
3
Recorrer todos los nodos
k = x (k
x
Dn
n
x
que se debe
a sí mismo es 0).
es el nodo actual).
adyacentes
de
k
(denominados
vi ),
excepto los
marcados como evaluados
4
Si la distancia desde
desde
x
hasta
k
x
hasta
vi
guardada en
sumada a la distancia desde
Di es mayor que la distancia
k hasta vi , ésta se sustituye
con la segunda nombrada, esto es:
si
Di > Dk + d(k, vi )
entonces
Di = Dk + d(k, vi )
5
Marcar como evaluadoa
6
El siguiente nodo actual es el de menor valor en
k.
Di
(puede hacerse
almacenando los valores en una cola de prioridad); volver a 3 mientras
existan nodos no evaluados.
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Algoritmo de Dijkstra: Ejemplo
Se añade
Mientras
AaQ
Q 6= Ø
Se escoge
D
v∈Q
con menor
y se marca como visitado
(sale de
Q)
Q
Se añaden a
los vecinos
v,
x
D de cada x
no marcados de
denominados
Se actualiza
si la distancia que
atraviesa a
v
hasta
x
es
menor que la distancia
hasta
x
anterior
Hugo Franco, PhD
Algoritmos sobre Grafos
de la iteración
Algoritmos basados en Árboles
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Árbol de Expansión
Spanning tree
Un árbol de expansión de un grafo es una estructura de datos en
árbol que toca todos los vértices del grafo
Sólo tienen sentido en grafos de un sólo componente (conexos)
Un árbol de expansión mínimo es un árbol de expansión cuya suma
de longitudes de los enlaces es tan pequeña como sea posible en un
grafo dado (puede haber más de uno)
Se llama tamaño del árbol de expansión a la suma de las
longitudes de los enlaces.
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Algoritmo de Prim
El algoritmo de Prim sobre un grafo permite construir el árbol de
expansión mínimo (MST) del mismo. Puede verse como una versión
simplicada del algoritmo de Dijkstra
1
2
Seleccionar un nodo arbitrario de inicio
s.
Inicializar el árbol
Repetidamente agregar el enlace más corto incidente a
T
T = s.
en cada
nodo (el enlace más corto que tiene un vértice dentro de los enlaces
de
T
y el otro no hasta que el árbol contenga todos los nodos
Hugo Franco, PhD
Algoritmos sobre Grafos
Deniciones
Algoritmos básicos de búsqueda
Algoritmos de ruta más corta
Algoritmos basados en árboles
Algoritmo de Kruskal
Otra forma de encontrar el árbol de expansión mínimo de un grafo
muy conocida es el Algoritmo de Kruskal.
La idea es la de ordenar los enlaces por longitud y examinar cada
uno de ellos del más corto al más largo. Se debe poner cada enlace
en un conjunto de subárboles si no forma un ciclo con los enlaces
escogidos con anterioridad
Hugo Franco, PhD
Algoritmos sobre Grafos