Download Grafos

Tema 5. Grafos.
5.1. Introducción, notación y definiciones.
5.2. Representación de grafos.
5.3. Recorridos sobre grafos.
5.4. Árboles de expansión mínimos.
5.5. Problemas de caminos mínimos.
5.6. Algoritmos sobre grafos dirigidos.
5.7. Algoritmos sobre grafos no dirigidos.
5.8. Otros problemas con grafos.
A.E.D.
Tema 5. Grafos.
1
5.1. Ejemplos de grafos.
• Ejemplo: Grafo de carreteras entre ciudades.
Oviedo
4
Zaragoza
39 5
32
19
3
Valladolid
296
1
0
15
Jaén
12
5
Cádiz
99
Sevilla
2
24
256
1 91
Valencia
241
335
Badajoz
25
Gerona
Barcelona
5
Madrid
3
40
0
0
1
34
9
Vigo
Bilbao
28
0
45
5
356
304
32
171
Coruña
278
Murcia
Granada
A.E.D.
Tema 5. Grafos.
2
5.1. Ejemplos de grafos.
• Ejemplo: Grafo de carreteras entre ciudades.
Problemas
• ¿Cuál es el camino más corto de Murcia a Badajoz?
• ¿Existen caminos entre todos los pares de
ciudades?
• ¿Cuál es la ciudad más lejana a Barcelona?
• ¿Cuál es la ciudad más céntrica?
• ¿Cuántos caminos distintos existen de Sevilla a
Zaragoza?
• ¿Cómo hacer un tour entre todas las ciudades en el
menor tiempo posible?
A.E.D.
Tema 5. Grafos.
3
5.1. Ejemplos de grafos.
• Ejemplo: Grafo de transiciones de un AFD.
b
b
inicio
0
a
1
b
2
b
3
a
a
a
A.E.D.
Tema 5. Grafos.
4
5.1. Ejemplos de grafos.
• Ejemplo: Grafo de transiciones de un AFD.
Problemas
• ¿La expresión: a b b a b a b b b a, es una
expresión válida del lenguaje?
• ¿Cuál es la expresión válida más corta?
• Transformar el grafo en una expresión regular y
viceversa.
A.E.D.
Tema 5. Grafos.
5
5.1. Ejemplos de grafos.
• Ejemplo: Grafo asociado a un dibujo de líneas.
Escena
Modelo 1
1
2
4
3
7
5
6
Modelo 2
b
a
c
e
d
A.E.D.
Tema 5. Grafos.
6
5.1. Ejemplos de grafos.
• Ejemplo: Grafo de asociado a un dibujo de líneas.
Problemas
• ¿Cuántos grupos hay en la escena?
• ¿Qué objetos están visibles en la escena y en qué
posiciones?
• ¿Qué correspondencia hay entre puntos del
modelo y de la escena observada?
• ¿Qué objetos son isomorfos?
A.E.D.
Tema 5. Grafos.
7
5.1. Introducción y definiciones.
• Un grafo G es una tupla G= (V, A), donde V es un
conjunto no vacío de vértices o nodos y A es un
conjunto de aristas o arcos.
• Cada arista es un par (v, w), donde v, w  V.
Tipos de grafos
v
• Grafo no dirigido.
Las aristas no están ordenadas:
(v, w) = (w, v)
• Grafos dirigidos (o digrafos).
v
Las aristas son pares ordenados:
<v, w>  <w, v>
<v, w>  w = cabeza de la arista, v = cola.
A.E.D.
Tema 5. Grafos.
w
w
8
5.1. Terminología de grafos.
• Nodos adyacentes a un nodo v: todos los nodos
unidos a v mediante una arista.
• En grafos dirigidos:
– Nodos adyacentes a v: todos los w con <v, w>  A.
– Nodos adyacentes de v: todos los u con <u, v>  A.
• Un grafo está etiquetado si cada arista tiene
asociada una etiqueta o valor de cierto tipo.
• Grafo con pesos: grafo etiquetado con valores
numéricos.
• Grafo etiquetado: G= (V, A, W), con W: A  TipoEtiq
A.E.D.
Tema 5. Grafos.
9
•
•
•
•
•
5.1. Terminología de grafos.
Camino de un vértice w1 a wq: es una secuencia
w1, w2, ..., wq  V, tal que todas las aristas (w1, w2),
(w2, w3), ..., (wq-1, wq)  A.
Longitud de un camino: número de aristas del
camino = nº de nodos -1.
Camino simple: aquel en el que todos los vértices
son distintos (excepto el primero y el último que
pueden ser iguales).
Ciclo: es un camino en el cual el primer y el último
vértice son iguales. En grafos no dirigidos las
aristas deben ser diferentes.
Se llama ciclo simple si el camino es simple.
A.E.D.
Tema 5. Grafos.
10
5.1. Terminología de grafos.
• Un subgrafo de G=(V, A) es un grafo G’=(V’, A’)
tal que V’V y A’A.
• Dados dos vértices v, w, se dice que están
conectados si existe un camino de v a w.
• Un grafo es conexo (o conectado) si hay un
camino entre cualquier par de vértices.
• Si es un grafo dirigido, se llama fuertemente
conexo.
• Un componente (fuertemente) conexo de un
grafo G es un subgrafo maximal (fuertemente)
conexo.
A.E.D.
Tema 5. Grafos.
11
5.1. Terminología de grafos.
• Un grafo es completo si existe una arista entre
cualquier par de vértices.
• Para n nodos, ¿cuántas aristas tendrá un grafo
completo (dirigido o no dirigido)?
• Grado de un vértice v: número de arcos que
inciden en él.
• Para grafos dirigidos:
– Grado de entrada de v: nº de aristas con <x, v>
– Grado de salida de v: nº de aristas con <v, x>
A.E.D.
Tema 5. Grafos.
12
5.1. Operaciones elementales con grafos.
•
•
•
•
•
Crear un grafo vacío (o con n vértices).
Insertar un nodo o una arista.
Eliminar un nodo o arista.
Consultar si existe una arista (obtener la etiqueta).
Iteradores sobre las aristas de un nodo:
para todo nodo w adyacente a v hacer
acción sobre w
para todo nodo w adyacente de v hacer
acción sobre w
Mucho menos frecuente
A.E.D.
Tema 5. Grafos.
13
5.2. Representación de grafos.
• Representación de grafos:
– Representación del conjunto de nodos, V.
– Representación del conjunto de aristas, A.
2
1
3
5
4
• Ojo: las aristas son relaciones “muchos a
muchos” entre nodos...
A.E.D.
Tema 5. Grafos.
14
5.2. Representación de grafos.
• Representación del conjunto de aristas, A.
– Mediante matrices de adyacencia.
M
1
1
2
3
T
T
2
3
4
T
T
3
T
4
5
2
1
T
T
5
5
4
T
– Mediante listas de adyacencia.
1
2
3
2
3
5
3
1
4
5
4
5
4
A.E.D.
Tema 5. Grafos.
15
5.2. Matrices de adyacencia.
tipo GrafoNoEtiq= array [1..n, 1..n] de booleano
• Sea M de tipo GrafoNoEtiq, G= (V, A).
• M[v, w] = cierto  (v, w)  A
2
1
3
M
1
2
1
T
T
2
T
T
3
4
4
5
5
3
T
T
T
T
T
5
T
T
T
4
T
T
• Grafo no dirigido  Matriz simétrica: M[i, j] = M[j, i].
• Resultado: se desperdicia la mitad de la memoria.
A.E.D.
Tema 5. Grafos.
16
5.2. Matrices de adyacencia.
• Grafos etiquetados:
tipo GrafoEtiq[E]= array [1..n, 1..n] de E
• El tipo E tiene un valor NULO, para el caso de no
existir arista.
1
M
3
2
4
0
2
2
4
2
3
4
3
1
2
2
3
3
1
0
4
2
4
• ¿Cómo serían los iteradores: para todo adyacente
a, y adyacente de? ¿Y contar número de aristas?
• ¿Cuánto es el tiempo de ejecución?
A.E.D.
Tema 5. Grafos.
17
5.2. Matrices de adyacencia.
Uso de memoria
• k2 bytes/etiqueta
• Memoria usada: k2n2
Ventajas
• Representación y operaciones muy sencillas.
• Eficiente para el acceso a una arista dada.
Inconvenientes
• El número de nodos del grafo no puede cambiar.
• Si hay muchos nodos y pocas aristas (a<<n2) se
desperdicia mucha memoria (matriz escasa).
A.E.D.
Tema 5. Grafos.
18
5.2. Listas de adyacencia.
tipo Nodo= entero (1..n)
tipo GrafoNoEtiq= array [1..n] de Lista[Nodo]
• Sea R de tipo GrafoNoEtiq, G= (V, A).
• La lista R[v] contiene los w tal que (v, w)  A.
2
1
3
4
5
1
1
2
4
2
1
2
3
3
2
4
4
1
3
2
4
5
5
5
• Grafo no dirigido  Las aristas están repetidas.
• Resultado: también se desperdicia memoria.
A.E.D.
Tema 5. Grafos.
19
5.2. Listas de adyacencia.
• Grafos etiquetados:
tipo GrafoEtiq[E]= array [1..n] de Lista[Nodo,E]
1
a
b
4
a
2
d
c
3
1
2 a
2
4 b
3
1 a
2 c
4 d
4
• ¿Cómo serían los iteradores: para todo adyacente
a, y adyacente de? ¿Y contar número de aristas?
• ¿Cuánto es el orden de complejidad? Se suponen:
n nodos y a aristas.
A.E.D.
Tema 5. Grafos.
20
5.2. Listas de adyacencia.
Uso de memoria
•
•
•
•
k1 bytes/puntero, k2 bytes/etiqueta o nodo
Memoria usada: k1(n+a) + 2k2a
Con matrices de adyacencia: k2n2
¿Cuál usa menos memoria?
Ventajas
• Más adecuada cuando a<<n2.
Inconvenientes
• Representación más compleja.
• Es ineficiente para encontrar las aristas que llegan
a un nodo.
A.E.D.
Tema 5. Grafos.
21
5.2. Listas múltiples de adyacencia.
• Alternativa: Usar estructuras de listas múltiples.
– Lista de arcos
de salida.
– Lista de arcos
de entrada
a
b
1
2
c
d
e
3
registros
de aristas
array de
nodos
a
b
c
d
e
sig_ent
valor
sig_sal
1
2
3
lista_ent lista_sal
A.E.D.
Tema 5. Grafos.
22
5.3. Recorridos sobre grafos.
• Idea similar al recorrido en un árbol.
• Se parte de un nodo dado y se visitan los vértices
del grafo de manera ordenada y sistemática,
moviéndose por las aristas.
• Tipos de recorridos:
– Búsqueda primero en profundidad. Equivalente
a un recorrido en preorden de un árbol.
– Búsqueda primero en amplitud o anchura.
Equivalente a recorrer un árbol por niveles.
• Los recorridos son una herramienta útil para
resolver muchos problemas sobre grafos.
A.E.D.
Tema 5. Grafos.
23
5.3. Recorridos sobre grafos.
• El recorrido puede ser tanto para grafos dirigidos
como no dirigidos.
• Es necesario llevar una cuenta de los nodos
visitados y no visitados.
var
marca: array [1, ..., n] de (visitado, noVisitado)
operación BorraMarcas
para i:= 1, ..., n hacer
marca[i]:= noVisitado
A.E.D.
Tema 5. Grafos.
24
5.3. Búsqueda primero en profundidad.
operación bpp (v: nodo)
marca[v]:= visitado
para cada nodo w adyacente a v hacer
si marca[w] == noVisitado entonces
bpp(w)
finpara
operación BúsquedaPrimeroEnProfundidad
BorraMarcas
para v:= 1, ..., n hacer
si marca[v] == noVisitado entonces
bpp(v)
finpara
A.E.D.
Tema 5. Grafos.
25
5.3. Búsqueda primero en profundidad.
• El recorrido no es único: depende del nodo inicial
y del orden de visita de los adyacentes.
• El orden de visita de unos nodos a partir de otros
puede ser visto como un árbol: árbol de
expansión en profundidad asociado al grafo.
• Si aparecen varios árboles: bosque de expansión
en profundidad.
• Ejemplo.
Grafo
no
dirigido.
1
2
4
7
3
9
6
5
8
A.E.D.
Tema 5. Grafos.
26
5.3. Búsqueda primero en profundidad.
• Bosque de expansión en profundidad
1
2
6
1º
4
7º
5
8º
2º
3º
7
9
3
4º
8
Arcos del
árbol
6º
5º
9º
Arcos no
del árbol
• Arcos no del árbol: si marca[v] == noVisitado ...
 se detectan cuando la condición es falsa.
A.E.D.
Tema 5. Grafos.
27
5.3. Búsqueda primero en profundidad.
• Ejemplo: Grafo dirigido.
b
c
Bosque de expansión
a
1º
Arco de
Arco de retroceso
cruce
e
d
a
b
2º
c
3º
d
4º
e
5º
Arco de
avance
• ¿Cuánto es el tiempo de ejecución de la BPP?
• Imposible predecir las llamadas en cada ejecución.
• Solución: medir el “trabajo total realizado”.
A.E.D.
Tema 5. Grafos.
28
5.3. Búsqueda primero en anchura (o amplitud).
• Búsqueda en anchura empezando en un nodo v:
– Primero se visita v.
– Luego se visitan todos sus adyacentes.
– Luego los adyacentes de estos y así sucesivamente.
• El algoritmo utiliza una cola de vértices.
• Operaciones básicas:
– Sacar un elemento de la cola.
– Añadir a la cola sus adyacentes no visitados.
operación BúsquedaPrimeroEnAnchura
BorraMarcas
para v:= 1, ..., n hacer
si marca[v] == noVisitado entonces
bpa(v)
A.E.D.
Tema 5. Grafos.
29
5.3. Búsqueda primero en anchura (o amplitud).
operación bpa (v: Nodo)
var C: Cola[Nodo]
x, y: Nodo
marca[v]:= visitado
InsertaCola (v, C)
mientras NOT EsVacíaCola (C) hacer
x:= FrenteCola (C)
SuprimirCola (C)
para cada nodo y adyacente a x hacer
si marca[y] == noVisitado entonces
marca[y]:= visitado
InsertaCola (y, C)
finsi
finpara
finmientras
A.E.D.
Tema 5. Grafos.
30
5.3. Búsqueda primero en anchura (o amplitud).
• Ejemplo.
Grafo no
dirigido.
1
2
4
6
3
9
7
5
8
• Bosque de expansión en anchura.
1
2
1º
2º
4
3
3º
5
6
4º
7
5º
8
6º
7º
8º
9
9º
Arcos de
cruce
A.E.D.
Tema 5. Grafos.
31
5.3. Búsqueda primero en anchura (o amplitud).
• Ejemplo: Grafo dirigido.
b
c
Bosque de expansión
a
b
1º
c
e
d
d
3º
2º
e
4º
5º
a
• ¿Cuál es el tiempo de ejecución de la BPA?
• ¿Cómo comprobar si un arco es de avance, cruce, etc.?
• Solución: Construir el bosque explícitamente.
A.E.D.
Tema 5. Grafos.
32
5.3. Recorridos sobre grafos.
• Construcción explícita del bosque de expansión:
Usamos una estructura de punteros al padre.
marca: array [1, ..., n] de entero
• marca[v] vale: -1 si v no está visitado
0 si está visitado y es raíz de un árbol
En otro caso indicará cuál es el padre de v
• Modificar BorraMarcas, bpp y bpa, para construir el
bosque de expansión.
– Arco de avance <v, w>: w es descendiente de v en uno
de los árboles del bosque.
– Arco de retroceso <v, w>: v es descendiente de w.
– Arco de cruce <v, w>: si no se cumple ninguna de las
anteriores.
A.E.D.
Tema 5. Grafos.
33
5.3. Ejemplos de aplicación de los recorridos.
• Problema 1: Encontrar los componentes conexos
de un grafo no dirigido.
1
3
10
8
2
7
6
4
9
5
• Problema 2: Prueba de aciclicidad. Dado un
grafo (dirigido o no dirigido) comprobar si tiene
algún ciclo o no.
A.E.D.
Tema 5. Grafos.
34
5.3. Ejemplos de aplicación de los recorridos.
• Prueba de aciclicidad.
– Grafo no dirigido. Hacer una BPP (o BPA). Existe algún
ciclo si y sólo si aparece algún arco que no es del árbol
de expansión.
– Grafo dirigido. Hacer una BPP (o BPA). Existe un ciclo
si y sólo si aparece algún arco de retroceso.
• Orden de complejidad de la prueba de aciclicidad: igual
que los recorridos.
– Con matrices de adyacencia: O(n2).
– Con listas de adyacencia: O(a+n).
A.E.D.
Tema 5. Grafos.
35
5.4. Árboles de expansión mínimos.
• Definición: Un árbol de expansión de un grafo G=(V,
A) no dirigido y conexo es un subgrafo
G’=(V, A’) conexo y sin ciclos.
• Ejemplo: los árboles de expansión en profundidad y
en anchura de un grafo.
• En grafos con pesos, el coste del árbol de
expansión es la suma de los costes de las aristas.
• Problema del árbol de expansión de coste mínimo:
Dado un grafo ponderado no dirigido, encontrar el
árbol de expansión de menor coste.
A.E.D.
Tema 5. Grafos.
36
5.4. Árboles de expansión mínimos.
2
3
1
2
6
3
5
4
5
6
• Problema: conectar todos los ordenadores con el menor
coste total.
• Solución: algoritmos clásicos de Prim y Kruskal.
A.E.D.
Tema 5. Grafos.
37
5.4. Algoritmo de Prim.
Esquema:
1. Empezar en un vértice cualquiera v. El árbol
consta inicialmente sólo del nodo v.
2. Del resto de vértices, buscar el que esté más
próximo a v (es decir, con la arista (v, w) de
coste mínimo). Añadir w y la arista (v, w) al árbol.
3. Buscar el vértice más próximo a cualquiera de
estos dos. Añadir ese vértice y la arista al árbol
de expansión.
4. Repetir sucesivamente hasta haber añadido los n
vértices.
A.E.D.
Tema 5. Grafos.
38
5.4. Algoritmo de Prim.
• La solución se construye poco a poco,
empezando con una solución “vacía”.
• Implícitamente, el algoritmo maneja los conjuntos:
– V: Vértices del grafo.
– U: Vértices añadidos a la solución.
– V-U: Vértices que quedan por añadir.
• ¿Cómo implementar eficientemente la búsqueda:
encontrar el vértice de V-U más próximo a alguno
de los de U?
A.E.D.
Tema 5. Grafos.
39
5.4. Algoritmo de Prim.
• Para calcular el siguiente vértice a coger se usan dos arrays:
– MAS_CERCANO: Para cada vértice de V-U indica el
vértice de U que se encuentra más próximo.
– MENOR_COSTO: Indica el costo de la arista más cercana
(almacenada en el array anterior).
Estructura del algoritmo de Prim
• Inicialmente U={1}  MAS_CERCANO[v] = 1.
MENOR_COSTO[v] = C[1, v]
Suponemos que C[v, w] (Matriz de costes) contiene el
coste de la arista (v, w)
• Buscar el valor v, con valor MENOR_COSTO mínimo.
Asignarle un valor muy grande (para no volver a cogerlo).
• Recalcular los valores MAS_CERCANO y MENOR_COSTO
de los demás nodos. Para cada w, comprobar si C[v, w] es
menor que MENOR_COSTO[w].
• Repetir los dos puntos anteriores hasta que se hayan añadido
los n vértices.
A.E.D.
Tema 5. Grafos.
40
5.4. Algoritmo de Prim.
• Resultados del algoritmo:
– Árbol de expansión: las aristas serán los pares (i, MAS_CERCANO[i]),
para i= 2, ..., n.
– Costo del árbol de expansión: Suma de los MENOR_COSTO[i], para
i= 2, ..., n (antes de asignarles un valor grande).
• Ejemplo. Mostrar la ejecución del algoritmo de Prim para el siguiente
grafo no dirigido.
5
1
1
6
5
2
5
3
4
6
5
4
1
2
6
3
1
4
2
5
2
3
4
6
3
6
5
• ¿Cuál es el orden de complejidad del algoritmo?
A.E.D.
Tema 5. Grafos.
41
5.4. Algoritmo de Kruskal.
• Dado un grafo ponderado G=(V, A), el algoritmo parte de
un grafo G’= (V, Ø). Cada nodo es una componente
conexa en sí misma.
• En cada paso de ejecución se elige la arista de menor
costo de A.
– Si une dos nodos que pertenecen a distintas
componentes conexas entonces se añade al árbol de
expansión G’.
– En otro caso no se coge, ya que formaría un ciclo en
G’.
• Acabar cuando G’ sea conexo: cuando tengamos n-1
aristas.
A.E.D.
Tema 5. Grafos.
42
5.4. Algoritmo de Kruskal.
Estructura del algoritmo de Kruskal
• Sea T de tipo Conjunto de aristas, el lugar donde se
guardarán las aristas del árbol de expansión. Asignar
Ø a T.
• Mientras T contenga menos de n-1 aristas hacer:
– Elegir la arista (v, w) de A con menor costo. Las
aristas deben estar ordenadas por coste.
– Borrar (v, w) de A (para no volver a cogerla).
– Si v, w están en distintos componentes conexos
entonces añadir (v, w) a T. En otro caso, descartar
(v, w). Necesitamos operaciones para saber si dos nodos
están en la misma componente conexa y para unir
componentes.
A.E.D.
Tema 5. Grafos.
43
5.4. Algoritmo de Kruskal.
• Ejemplo.
5
1
1
6
5
2
5
3
5
1
4
4
6
4
1
2
6
3
1
4
2
2
3
6
6
5
2
3
4
6
3
5
5
• Relación dos nodos pertenecen a una componente conexa:
es una relación binaria de equivalencia  podemos usar la
estructura de representación para relaciones de
equivalencia (con operaciones Inicia, Encuentra y Unión).
• ¿Cuál es el orden de complejidad del algoritmo?
A.E.D.
Tema 5. Grafos.
44
5.5. Problemas de caminos mínimos.
• Definición: Dado un grafo ponderado G= (V, A) (dirigido o
no) y un camino w1, w2, ..., wq en G, el costo del camino
será la suma de los costos asociados a las aristas (w1,
w2), ..., (wq-1, wq).
• Si el grafo es no ponderado, normalmente el costo se
asocia con la longitud del camino.
• Problema de los caminos más cortos por un origen:
Encontrar los caminos más cortos entre un nodo origen
dado a todos los demás nodos.
A.E.D.
Tema 5. Grafos.
45
5.5. Algoritmo de Dijkstra.
• Supongamos un grafo ponderado G (con pesos  0) y un
nodo origen v.
• El algoritmo trabaja con dos conjuntos:
– S: conjunto de nodos escogidos, para los cuales se
conoce el camino de distancia mínima al origen.
– C: conjunto de nodos candidatos, pendientes de
calcular el camino mínimo. Conocemos los caminos
mínimos al origen pasando por nodos de S.
• En cada paso coger del conjunto de candidatos el nodo con
distancia mínima al origen. Recalcular los caminos de los
demás candidatos pasando por el nodo cogido.
• Un camino especial del origen a otro nodo cualquiera es un
camino que sólo pasa por nodos ya escogidos.
• Supongamos que el nodo origen es el 1.
A.E.D.
Tema 5. Grafos.
46
5.5. Algoritmo de Dijkstra.
• En un array D[2, ..., N] se guarda la longitud del camino
especial más corto a cada vértice. Cuando todos los nodos
estén en S, todos los caminos son especiales y D contiene
las distancias mínimas al origen.
• En otro array P[2, ..., N] se almacena el camino por el que
pasa cada nodo v. El camino de 1 a v pasa por P[v].
• Inicialmente D contendrá los caminos directos de 1 a los
restantes nodos, es decir d[1, x]. Si no existe la arista (1, x)
el costo será .
P contendrá el valor 1 (el camino es directo). S contendrá
sólo el nodo 1.
• Buscar el nodo v de C=V-S con mínimo valor de D. Añadir v
a S. Para el resto de nodos comprobar si el camino al origen
es más corto pasando por el nodo v:
si D[v]+d[v, w] < D[w]
D[w]:= D[v] + d[v, w]
P[w]:= v
A.E.D.
47
Tema 5. Grafos.
5.5. Algoritmo de Dijkstra.
para i:= 2, ..., N
S[i]:= FALSO
D[i]:= d[1, i]
P[i]:= 1
para i:= 1, ..., N-1
v:= vértice con D[v] mínimo y S[v]=FALSO
S[v]:= VERDADERO
para cada nodo w adyacente a v
si S[w]=FALSO
si D[v]+d[v, w]<D[w]
D[w]:= D[v]+C[v, w]
P[w]:= v
Operación ImprimeCamino (v:entero)
si v != 1
ImprimirCamino(P[v])
escribir v
A.E.D.
Tema 5. Grafos.
48
5.5. Algoritmo de Dijkstra.
• Ejemplo:
2
1
4
1
2
3
2
5
4
6
2
3
4
5
6
7
10
3
4
8
5
Nodo
2
6
7
1
S D P
S D P
S D P
S D P
S D P
F
F
F
F
F
F
F
F
T
F
F
F
T
F
T
F
F
F
T
T
T
F
F
F
T
T
T
T
T
T
2

1



1
1
1
1
1
1
Inicializ.
2
3
1
3
9
5
v=4
1
4
1
4
4
4
2
3
1
3
9
5
1
4
1
4
4
4
v=2
A.E.D.
Tema 5. Grafos.
2
3
1
3
8
5
1
4
1
4
3
4
v=3
.....
5, 7
2
3
1
3
6
5
1
4
1
4
7
4
v=6
49
5.5. Algoritmo de Dijkstra, complejidad.
• Matrices de adyacencia:
– Inicialización: O(n).
– Ejecutar n-1 veces:
• Buscar el elemento con D[v] mínimo y S[v] falso: O(n).
• Actualizar los valores de los nodos candidatos: O(n).
– En total tenemos O(n2).
• Listas de adyacencia:
– Inicialización: O(n).
– La actualización de los candidatos se limita a los nodos que son
adyacentes a v. En total la actualización se hace O(a) veces.
– La búsqueda del elemento sigue requiriendo O(n) pasos, por lo que
el orden total sería O(n2).
– Modificación: usar una estructura ordenada para guardar los nodos
candidatos (por ejemplo un árbol binario). La búsqueda requiere
O(log n) en cada paso, en total O(n*log n). Además, en la
actualización un nodo podría cambiar de posición en el árbol, luego
requiere O(a*log n).
– En total, requiere O((a+n)*log n).
2.
– Esta modificación será adecuada
cuando
a<<n
A.E.D.
50
Tema 5. Grafos.
5.5. Caminos mínimos entre todos los vértices.
• Aplicando el algoritmo de Dijkstra n veces: O(n3) ó O((a+n)*n*log
n).
Algoritmo de Floyd
• Utiliza una matriz de adyacencia D[v, w], que será la matriz de
costos.
• Inicialmente D[v, w] contendrá los costos de las aristas C[v, w].
• En cada paso k, en la posición D[v, w] estará la longitud del
camino óptimo que contiene nodos sólo de los k primeros.
• Al final del algoritmo, D almacenará los costos de los caminos
mínimos.
• En el paso k, el nodo k actúa de pivote. Calcular, para cada
camino de v a w, si es más corto pasando por k.
– Dk[i, j]= min (Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j]), para todo ij.
– Dk[i, k]= min (Dk-1[i, k], Dk-1[i, k] + Dk-1[k, k])  la fila y la columna k
no varían en el paso k, luego sólo necesitamos una matriz D.
A.E.D.
Tema 5. Grafos.
51
5.5. Algoritmo de Floyd.
operación Floyd (C: array [1..N, 1..N] de entero)
var
k, i, j: entero
D: array [1..N, 1..N] de entero
2
8
1
3
para i:= 1, ..., N
para j:= 1, ..., N
D[i, j]:= C[i, j]
para k:= 1, ..., N
{ k es el pivote }
para i:= 1, ..., N
para j:= 1, ..., N
D[i, j]:= min (D[i, j], D[i, k] + D[k, j])
2
2
3
5
• Tenemos los costos de los caminos mínimos, ¿cómo saber
cuáles son los caminos?
A.E.D.
Tema 5. Grafos.
52
5.5. Algoritmo de Floyd.
• Igual que en Dijkstra, una matriz P de NxN almacena el
camino. P[i, j]=0 si el camino es directo. En otro caso, el
camino de i a j pasa por P[i, j].
si D[i, k] + D[k, j] < D[i, j]
D[i, j]:= D[i, k] + D[k, j]
P[i, j]:= k
Para escribir el camino:
operación Camino (i, j: integer)
k:= P[i, j]
si k!= 0
Camino (i, k)
escribir k
Camino (k, j)
• ¿Cuál es el orden de complejidad del algoritmo de Floyd?
A.E.D.
Tema 5. Grafos.
53
5.5. Cierre transitivo.
Dada una matriz de adyacencia M de un grafo dirigido,
obtener una matriz A de valores booleanos en la que A[i, j]
indica si existe o no un camino de i a j.
Algoritmo de Warshall
• Es parecido al algoritmo de Floyd. En lugar de enteros
(costos) trabajamos con booleanos (existe arista o no).
• Inicialmente A=M. En cada paso k: A[i, j]:= A[i, j] or (A[i, k]
and A[k, j]).
A.E.D.
Tema 5. Grafos.
54
5.6. Algoritmos sobre grafos dirigidos.
Componentes fuertemente conexos
• Un componente conexo de un grafo G es un subgrafo conexo (y
maximal) de G. Es decir, contiene un conjunto de vértices para
los cuales existen caminos entre cualquier par de nodos (v, w) y
(w,v).
1
2
4
• Ejemplo. Grafo G no dirigido.
5
3
6
7
9
8
Componente conexo 2
Componente conexo 1
• Cálculo de componentes conexos en grafos no dirigidos:
Realizar un recorrido en profundidad. Cada árbol generado es un
componente conexo.
• Si el grafo es dirigido, entonces hablamos de componentes
fuertemente conexos.
• En grafos dirigidos no es suficiente con realizar una búsqueda
A.E.D.
55
primero en profundidad.
Tema 5. Grafos.
5.6. Componentes fuertemente conexos.
Algoritmo para encontrar los componentes fuertemente conexos de
un grafo dirigido G.
1. Realizar la búsqueda en profundidad de G, numerando los vértices
en el orden de terminación de las llamadas recursivas (al final de
bpp).
2. Construir un nuevo grafo dirigido GR invirtiendo las direcciones de
los arcos. Para todo <v, w>  A(G), <w, v>  A(GR).
3. Realizar una búsqueda en profundidad en GR partiendo del nodo
con numeración más alta. Si en el recorrido no se visitan todos los
nodos, iniciar la búsqueda en profundidad a partir del nodo no
visitado con numeración más alta.
4. Cada árbol del bosque abarcador resultante es un componente
fuertemente conexo de G.
• Ejemplo.
B
D
C
E
A
A.E.D.
Tema 5. Grafos.
56
5.6. Componentes fuertemente conexos.
B
A 5
B
C
4
A
C
A
3
E 2
D
D
C
E
E
D
B
1
• Podemos representar las relaciones entre componentes mediante un
grafo reducido.
• Grafo reducido de un grafo dirigido G: es un grafo dirigido en el
que cada nodo representa un componente fuertemente conexo de G,
y existirá una arista entre un nodo y otro si existe una arista entre
algunos de los nodos de los componentes conexos de G
correspondientes.
A, B, C
A.E.D.
Tema 5. Grafos.
D, E
57
5.6. Grafos dirigidos acíclicos.
• Definición: un grafo dirigido acíclico (GDA) es un grafo
dirigido y sin ciclos.
• Ejemplos: estructura de directorios (con posibilidad de enlaces
simbólicos), representación de expresiones aritméticas (con
subexpresiones comunes), prerrequisitos para realizar un curso, grafo
de actividades para planificación de tareas.
*
Cimientos (3)
Techo (2)
+
+
A
Paredes (4)
inicio
B
D
*
Jardín (2)
Fachada (2)
Comprar
ventanas (5)
(A+B)*(D+D*(A+B))
final
• Representación de órdenes parciales. Un orden parcial en un
conjunto S es una relación binaria que cumple:
– Para cualquier elemento a de S, (a R a) es falso.
– Para cualquier a, b, c de S, si (a R b) y (b R c) entonces (a R c).
• Ejemplo. La relación de inclusión propia entre conjuntos ().
A.E.D.
Tema 5. Grafos.
58
5.6. Ordenación topológica en grafos dirigidos
acíclicos.
• Recorrido en orden topológico: es un tipo de recorrido
aplicable solamente a GDAs. Un vértice sólo se visita después de
haber sido visitados todos sus predecesores en el grafo.
• Este recorrido da lugar a una ordenación topológica: a cada
nodo se le asigna un número num_top(v), tal que si existe una
arista <i, j> entonces num_top(i) < num_top(j). En general puede
existir más de un orden válido.
• Ejemplos:
– El orden: Cimientos, Paredes, Techo, Jardín, Comprar ventanas, Fachada,
es una posible ordenación topológica del grafo de tareas.
– En una expresión aritmética, el orden topológico a la inversa, es el orden
para evaluar el resultado total de la expresión.
A.E.D.
Tema 5. Grafos.
59
5.6. Ordenación topológica en grafos dirigidos
acíclicos.
• Implementación del recorrido en orden topológico.
1. Calcular los grados de entrada de todos los nodos.
2. Buscar un nodo v con grado de entrada 0 (es decir sin
predecesores, si no hay ninguno es porque existe un ciclo).
Marcarlo como visitado.
3. Para todos los nodos adyacentes a v, decrementar en 1 su
grado de entrada.
4. Repetir los pasos 2 y 3 hasta haber visitado todos los nodos.
A.E.D.
Tema 5. Grafos.
60
5.6. Algoritmos sobre grafos dirigidos.
Grafos dirigidos acíclicos
operación OrdenTopológico(G: grafo; var num_top: array [1..N] de enteros)
var C: Cola(nodo) ; contador: entero ; v, w: nodo
Anula (C)
contador:= 1
para cada nodo v
si GradoEnt[v] = 0
InsertaCola(v, C)
3
mientras NO EsVacíaCola(C)
v:= FrenteCola(C)
SuprimirCola(C)
num_top[v]:= contador
contador:= contador + 1
para cada w adyacente a v
GradoEnt[w]:= GradoEnt[w]-1
si GradoEnt[w] = 0
InsertaCola(v, C)
1
2
4
6
5
7
• ¿Cuál es el orden de complejidad del algoritmo, con matrices y listas
de adyacencia?
A.E.D.
Tema 5. Grafos.
61
5.6. Flujo máximo en redes.
• Supongamos un grafo dirigido G=(V, A) con pesos en las aristas. El peso
de una arista C(v, w) representa el número máximo de unidades que
pueden “fluir” desde el nodo v al w.
•
Por ejemplo: C(v, w) puede ser la cantidad máxima de agua que puede ir por
una tubería que comunica v con w, o el número de coches máximo que cabe en
una calle.
• Problema de flujo máximo.
Dado un nodo origen s y un nodo destino t en un grafo dirigido con
pesos, encontrar la cantidad máxima de flujo que puede pasar de s a t.
2
s
1
3
•
•
b
a
2
d
4
3
2
3
t
c
s
0
3
2
b
a
2
d
3
1
2
t
c
2
La suma de entradas para cada nodo interior debe ser igual a la suma de salidas.
Los valores de flujo en cada arista no pueden superar los valores máximos.
A.E.D.
62
Tema 5. Grafos.
5.6. Flujo máximo en redes.
Algoritmo para calcular el flujo máximo.
1. Inicializar un grafo de flujo Gf con los mismos nodos y aristas de
G, pero con pesos 0. Este grafo guardará el resultado del
algoritmo.
2. Buscar un camino en G, desde s hasta t (camino creciente). Sea
m el valor mínimo de los costes de las aristas por las que pasa
el camino (por este camino pueden fluir hasta m unidades de
flujo).
3. Para cada arista (v, w) del camino, añadir al costo de la arista
correspon-diente en Gf el valor m: Cf[v, w] = Cf[v, w] + m.
4. Decrementar el valor m en cada arista (v, w) del camino, en el
grafo G. Si la arista toma el valor 0, eliminarla de G.
5. Volver al paso 2 mientras sigan existiendo caminos entre s y t
en G.
• Ejemplos:
– Caso 1: (s, b, d, t) con m=2; (s, a, c, t) con m=2; (s, a, d, t) con m=1. FIN
– Caso 2: (s, a, d, t) con m=3. FIN
•
El algoritmo no garantiza una solución óptima.
A.E.D.
Tema 5. Grafos.
63
5.6. Flujo máximo en redes.
•
Solución: en el paso 4 añadir una arista <w, v> a G con costo m (para
permitir deshacer los caminos).
2
0
a
5
s
b
4
4
1
4
3
s
0
4
t
3
3
s
a
2
s
4
2
0
b
3
0
d
c
31
a
2
t
s
2
20
4
t
0
2
c
A.E.D.
Tema 5. Grafos.
b
2
0
4
2
0
0
d
c
4
42
t
0
2
02
1
4
4
0
20
53
0
b
4
2
d
c
a
0
4
4
40
d
c
40
b
1
t
0
40
s
0
0
2
a
5
b
0
0
0
2
d
c
0
t
3
a
d
2
64
5.7. Algoritmos en grafos no dirigidos.
Puntos de articulación
• Definición: un punto de articulación de un grafo no dirigido G
es un nodo v tal que cuando es eliminado de G (junto con las
aristas incidentes en él) se divide un componente conexo del
grafo original en dos o más componentes conexos.
• Ejemplo. Si el grafo representa una red de ordenadores, un punto de
articulación será un nodo que si no funciona, hará que otros
ordenadores de la red queden incomunicados.
a
c
b
g
d
e
A.E.D.
Tema 5. Grafos.
f
65
5.7. Componentes biconexos.
• Definición: un grafo no dirigido se dice que es biconexo
si no tiene puntos de articulación.
• Definición: un grafo G tiene conectividad k si la
eliminación de k-1 nodos (con sus aristas) no desconecta
el grafo.
• Un grafo es biconexo si y sólo si tiene conectividad 2 o
más.
• El cálculo de los puntos de articulación se basa en un
recorrido en profundidad.
A.E.D.
Tema 5. Grafos.
66
5.7. Algoritmos para localizar los puntos de
articulación.
1. Realizar
una búsqueda primero en profundidad, numerando
los nodos en el orden en que son recorridos. En el array
numero_bpp[1..N] guardamos el orden de cada nodo.
2. En los puntos de terminación de las llamadas recursivas de
bpp (orden posterior) calcular los valores bajo[v] para cada
nodo, según la fórmula:
bajo[v] = mínimo (numero_bpp[v],
numero_bpp[z] | tal que exista un arco de retroceso (z, v),
bajo [y] | para todo y hijo de v en el árbol generado)
3. La raíz es un punto de articulación si y sólo si tiene dos o más
hijos en el árbol abarcador en profundidad.
4. Un nodo v, distinto de la raíz, es un punto de articulación si y
sólo si tiene algún hijo w en el árbol tal que bajo[w] 
numero_bpp[v].
A.E.D.
Tema 5. Grafos.
67
5.7. Puntos de articulación.
• Ejemplo.
a
a
n_bpp[b] = 2
bajo[b] = 1
c
b
b
g
d
e
f
n_bpp[d] = 3
bajo[d] = 1
n_bpp[e] = 4
bajo[e] = 1
d
e
n_bpp[a] = 1
bajo[a] = 1
c
n_bpp[c] = 5
bajo[c] = 5
n_bpp[f] = 6
f bajo[f] = 5
n_bpp[g] = 7
g bajo[g] = 5
a es la raíz y tiene dos hijos  a es un punto de articulación
c tiene un hijo f tal que bajo[f]=5  n_bpp[c]=5  c es un punto de articulación
• bajo[v] indica el menor valor de bpp alcanzable desde v hasta algún
descendiente y luego a través de un arco de retroceso.
• Si se cumple la condición del punto 4 (bajo[w]  numero_bpp[v], para
algún hijo w de v), si eliminamos v entonces w y sus descendientes no
pueden alcanzar los nodos antecesores de v.
A.E.D.
Tema 5. Grafos.
68
5.7. Circuitos de Euler.
• Un grafo no dirigido representa un dibujo de líneas. Cada nodo
del grafo representa un punto del dibujo y una arista entre dos
nodos indica que existe una línea entre los dos puntos
correspondientes.
1
3
2
4
6
5
1
3
2
4
6
5
7
• ¿Es posible dibujar estas figuras con un bolígrafo, pintando cada línea
una sola vez, sin levantar el bolígrafo y acabando donde se empezó?
• Circuito de Euler: es un ciclo (no necesariamente simple) que visita
todas las aristas exactamente una vez.
A.E.D.
Tema 5. Grafos.
69
5.7. Circuitos de Euler.
• Condiciones necesarias para que exista un circuito de Euler:
– El grafo debe ser conexo.
– Todos los nodos deben tener grado (número de aristas) par, ya que el
camino entra y sale de los nodos.
• Estas condiciones necesarias son también suficientes.
Algoritmo para encontrar un circuito de Euler en un grafo G,
partiendo de un nodo v.
1. Buscar un ciclo en G empezando por v (por ejemplo con
una búsqueda en profundidad). Puede que no todas las
aristas hayan sido visitadas.
2. Si quedan aristas por visitar, seleccionar el primer nodo
w del ciclo anterior que tenga una arista sin visitar.
Buscar un ciclo partiendo de w que pase por aristas no
visitadas.
3. Unir el ciclo del paso 1 con el obtenido en el paso 2.
Repetir sucesivamente los pasos 2 y 3 hasta que no
queden aristas por visitar.
A.E.D.
Tema 5. Grafos.
70
5.7. Circuitos de Euler.
Ejemplo.
1
3
2
Paso 1. Ciclo: (1, 2, 5, 7, 6, 3, 1)
4
6
5
1
7
3
2
4
Paso 2. Ciclo: (2, 3, 4, 2)
6
5
7
1
3
2
4
Paso 3. Ciclo: (1, 2, 3, 4, 2, 5, 7, 6, 3, 1)
1
Paso 2. Ciclo: (4, 5, 6, 4)
6
5
3
2
7
4
6
5
1
7
3
2
Paso 3. Ciclo: (1, 2, 3, 4, 5, 6, 4, 2, 5, 7, 6, 3, 1)
4
6
5
A.E.D.
Tema 5. Grafos.
7
71
5.8. Otros problemas con grafos.
• Problemas NP, de los que no se conocen algoritmos
“eficientes” para solucionarlos.
• La solución se basa normalmente en una búsqueda
exhaustiva en el espacio de soluciones, produciéndose
explosión combinatoria.
• Se puede encontrar solución aproximada por medio de
algoritmos heurísticos.
• A partir de la solución inicial se puede realizar una
búsqueda local para intentar mejorar la solución.
A.E.D.
Tema 5. Grafos.
72
5.8. Problema del ciclo hamiltoniano.
• Dado un grafo no dirigido G, un ciclo hamiltoniano es un
ciclo simple que visita todos los vértices.
• Problema del ciclo hamiltoniano.
Determinar si un grafo no dirigido dado tiene un ciclo
hamiltoniano.
1
1
2
3
4
5
2
3
6
4
5
6
• Aunque el problema es muy parecido al del circuito de
Euler, no se conoce ningún algoritmo para resolverlo en
tiempo polinomial.
A.E.D.
Tema 5. Grafos.
73
5.8. Problema del viajante.
• Dado un grafo no dirigido, completo y ponderado G = (V,
A), encontrar un ciclo simple de costo mínimo.
10
1
2
45
5
25
40
55
30
25
50
4
20
3
15
• Ejemplos: Un repartidor de determinadas mercancías tiene encargos
en varias ciudades. ¿Qué ruta debe seguir para que el costo de
desplazamiento sea mínimo?
• El problema del viajante es un problema NP-completo, con un orden
de complejidad exponencial. No existe una solución polinómica.
• Podemos aplicar heurísticas, obteniendo soluciones aproximadas, no
necesariamente óptimas.
A.E.D.
Tema 5. Grafos.
74
5.8. Coloración de grafos.
• Un grafo no dirigido G representa elementos, y una arista (v,
w) representa una incompatibilidad entre los elementos v y w.
• La coloración de un grafo consiste en la asignación de un
color (o etiqueta) a cada nodo, de forma que dos nodos
incompatibles no tengan el mismo color.
• Problema de coloración de grafos:
Realizar una coloración del grafo utilizando un número
mínimo de colores.
D
E
C
B
A
• Ejemplo. Un grafo se emplea para representar trayectorias (en una
intersec-ción de calles) e incompatibilidades entre ellas. El objetivo es
diseñar un sistema de semáforos con un número mínimo de estados.
Cada estado será un color resultante del algoritmo de coloración.
A.E.D.
Tema 5. Grafos.
75
5.8. Isomorfismo de grafos.
• Comparación de grafos: Dados dos grafos G=(Vg, Ag) y
F=(VF, AF), determinar si son iguales o no.
• La comparación se puede realizar fácilmente, comprobando
si se cumple que Vg= VF y Ag= AF.
• Isomorfismo de grafos: Dos grafos G=(Vg, Ag) y F=(VF, AF)
se dice que son isomorfos si existe una asignación de los
nodos de Vg con los nodos de VF tal que se respetan las
aristas.
1
3
2
4
b
a
c
d
• El isomorfismo de grafos es también un problema NP-completo,
la solución consistiría básicamente en comprobar todas las
posibles asignaciones.
A.E.D.
Tema 5. Grafos.
76