El TAD Grafo

Tema 4

! Esta representación resulta útil cuando el número de vértices se conoce previamente y permanecerá fijo durante la resolución del problema, pero resulta ineficiente si necesitamos añadir o eliminar vértices en tiempo de ejecución ! Por tanto, para un caso más general, podemos utilizar, en lugar de una tabla, una lista enlazada para almacenar la información de los vértices

tipo adyacencia = clase tipo grafo = clase

público

público

{ métodos tipo set/get }

{ métodos comunes a grafos }

privado v: vértice adyacentes: lista fclase

privado G: lista ; fclase

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

20

El TAD Grafo

Tema 4

Sevilla Huelva

Córdoba Cádiz

G Huelva

Sevilla

Sevilla

Huelva

Cádiz

Huelva

Cádiz

Córdoba

Córdoba

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

21

El TAD Grafo

Tema 4

4.3.3 Listas múltiples de adyacencia ! Se utilizan para grafos dirigidos, si lo que queremos saber es, de forma eficiente, los antecesores de un determinado nodo ! Se utiliza otra tabla de listas cuya lista i-ésima contiene los vértices antecesores al vértice i. Dicha lista se conoce con el nombre de lista de antecesores ! Una lista múltiple de adyacencia es una estructura de datos que une ambas tablas en una única estructura ! Hay un nodo por cada arista del grafo ! Cada nodo guarda la información de dos vértices (origen y destino de la arista) y dos punteros "

el primero apunta al nodo que almacena la siguiente arista que tiene el mismo vértice destino

"

el segundo apunta al nodo que almacena la siguiente arista que tiene el mismo vértice origen

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

22

El TAD Grafo

Tema 4

constante n = ... { cardinal de V } PtrNodoGM= puntero a NodoGM tipo grafoDirigido = clase público { métodos comunes a grafos } privado adyacentes, antecesores: tabla [1..n] de PtrNodoGM fclase tipo nodoGM = clase público { métodos de tipo set/get } privado origen, destino: vértice sigAnt, sigAdy: PtrNodoGM fclase

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

23

El TAD Grafo

Tema 4

1

3

origen

destino mismo origen

2 mismo destino

4

1

2

3

4

5 listas de listas de adyacencia antecesores inversa

·

5

1

2

2

1

2

3

5

2

5

3

1 2

2

4

3 · 4 · 5 listas de adyacencia

Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

24

El TAD Grafo

Eficiencia de las operaciones nV: número de vértices nA: número de aristas gE: grado máximo de entrada gS: grado máximo de salida

Operación

Matriz

Lista Simple

Lista Múltiple

creaGrafoVacío insertaArista eliminaArista estaArista adyacentes antecesores

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

25

Tema 4

El TAD Grafo: recorridos

4.4 Recorrido de un grafo

!

La operación de recorrer un grafo consiste en visitar todos aquellos vértices, a partir de un vértice determinado, y que son accesibles desde él en un determinado orden

!

Existen básicamente dos estrategias de recorrido: " en anchura " en profundidad ambos necesitan una estructura auxiliar para almacenar los vértices visitados ya que deben evitarse las visitas reiteradas

Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

26

El TAD Grafo: recorridos

4.4.1 Recorrido en anchura ! Consiste en visitar el vértice de partida V, y a continuación visitar, en anchura, los adyacentes que aún no hayan sido visitados ! Este método utiliza una cola como estructura auxiliar para mantener los vértices que se vayan a procesar posteriormente ! Los pasos son: 1. 2. 3. 4.

Guardar en la cola el vértice de partida y marcarlo como procesado Repetir los pasos 3 y 4 hasta que la cola esté vacía Retirar el nodo frente de la cola (F) y visitar F Guardar en la cola todos los vértices adyacentes al vértice de F que no estén procesados y marcarlos como procesados

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

27

El TAD Grafo: recorridos

Tema 4

Ejemplo

B

Vértices recorridos desde D

Estado de la cola Frente

A

Final

D H C

T R

Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

28

El TAD Grafo: recorridos

4.4.2 Recorrido en profundidad

! Consiste en visitar el vértice de partida V, y a continuación visitar, en profundidad, los adyacentes que aún no hayan sido visitados ! Generalización del recorrido en preorden de los árboles ! Este método utiliza una pila como estructura auxiliar para mantener los vértices que se vayan a procesar posteriormente ! Los pasos son: 1. 2. 3. 4.

Guardar en la pila el vértice de partida y marcarlo como procesado Repetir los pasos 3 y 4 hasta que la pila esté vacía Desapilar el nodo que está en la cima (C) y visitar C Guardar en la pila todos los vértices adyacentes al vértice de C que no estén procesados y marcarlos como procesados

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

29

El TAD Grafo: recorridos

Tema 4

Ejemplo

Vértices recorridos desde D

B

Estado de la pila Fondo

A

Cima

D H C

T R

Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

30

El TAD Grafo: caminos mínimos

4.5 Caminos mínimos sobre grafos ! Uno de los problemas que se plantea con frecuencia en los grafos es determinar el camino más corto entre un par de vértices. Este problema se plantea, generalmente, para grafos dirigidos y valorados (con factor de peso en las aristas) ! Suponemos que cada arista tiene asociada un coste cij no negativo, es decir, (vi, vj) # cij ≥ 0 ! El coste de un camino C = v1, v2, ..., vk es la suma de los costes de las aristas de C k −1

coste(C ) = ∑ coste( vi , vi + 1) i =1

! El objetivo es encontrar el camino desde v1 a vk con coste mínimo

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

31

Tema 4

El TAD Grafo: caminos mínimos

4.5.1 Algoritmo de Dijkstra ! Este algoritmo resuelve el problema de encontrar el camino de coste mínimo desde un vértice al resto de los vértices del grafo ! Es un algoritmo voraz, es decir, va seleccionando, en cada paso, la mejor solución entre las disponibles. En cada iteración se escoge aquel de los vértices por visitar más próximo a v. El algoritmo acaba cuando no quedan vértices por visitar ! Para que el algoritmo funcione correctamente, el grafo G=(V,A) tiene que ser dirigido, valorado y con factores de peso positivos ! Para indicar que no existe camino desde el vértice v1 hasta el vértice v2 usaremos la indeterminación ∞ ! Para mantener, en cada paso, la distancia mínima desde el origen podemos usar una tabla llamada D (distancia), que mantiene la distancia desde el origen a cada vértice del grafo

! En cada iteración, una vez seleccionado de entre los vértices por visitar, el vértice w más próximo a v se actualiza la tabla D para aquellos vértices u que son adyacentes de w y que cumplen que D [w] + peso(G, w, u) < D [u]

Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

32

El TAD Grafo: caminos mínimos

función Dijkstra (G:grafo; v: vértice; var A: tabla [1..n] de natural): tabla [1..n] de natural; var T: conjunto ; D: tabla [1..n] de natural; u,w: vértice; costeMin: natural; fvar T:=∅; • El vector D almacena las distancias mínimas para todo w en G hacer D[w]:= ∞; A[w]:= 0; T:= T ∪ {w}; fpara; D[v]:= 0; repetir n-1 veces costeMin:= ∞; para todo u en T hacer si D[u] ≤ costeMin entonces w:= u; costeMin:= D[u]; fsi; fpara; T:= T - {w}; para todo u en T hacer si D[w] + peso(G,w,u) < D[u] entonces D[u]:= D[w] + peso(g,w,u); A[u]:= w; fsi; fpara; frepetir, devuelve D; ffunción Algoritmos y Estructuras de Datos II

• El vector A almacena el antecesor inmediato en el camino mínimo • T es el conjunto de vértices que quedan por visitar

se inicializa D a un valor máximo. En A ponemos el valor 0 para indicar que aún no hay antecesores en el camino mínimo se elige de T el vértice con menor distancia a v, y se almacena en w se marca w como vértice tratado se recalculan las nuevas distancias mínimas de los adyacentes de w y se almacena en P el antecesor inmediato, es decir, el vértice con el que se forma el camino más corto

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

33

El TAD Grafo: caminos mínimos

Tema 4

v1

v2

5 2

v1

∞

0 2

5 2

v3

2

∞ v5

Iteración

2 v3

∞

3

v2

5

0

1

2

2

∞

4

v4

3 v5

Tratados

1

2

3

5

2

5

∞

4

T

v4

D[2]

D[3]

D[4]

D[5]

Inicial 1 2 3 4 P[1] =

P[2] =

Algoritmos y Estructuras de Datos II

Tema 4

P[3] =

P[4] =

I.T. en Informática de Gestión/Sistemas

P[5] =

Universidad de Huelva

34

El TAD Grafo: caminos mínimos

4.5.2 Algoritmo de Floyd ! En algunas aplicaciones puede resultar interesante determinar el camino mínimo entre todos los pares de vértices de un grafo dirigido valorado. El problema podría resolverse aplicando reiteradamente el algoritmo de Dijkstra, lo que resultaría demasiado costoso. La otra posibilidad es utilizar un método más directo conocido como el algoritmo de Floyd

! Sea G un grafo dirigido y valorado. Suponemos que los vértices están numerados de 1 a n. En este caso, utilizamos una matriz con los pesos de las aristas, de tal forma que cada elemento representa el peso cij asociado a cada arista (vi,vj). Utilizaremos cij = ∞ para representar que no existe arista entre los vértices vi y vj

! La idea principal consiste en encontrar la matriz D de n x n elementos, de tal forma que cada elemento Dij sea el coste mínimo de los caminos entre vi y vj

Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

35

Tema 4

El TAD Grafo: caminos mínimos

! El algoritmo comienza con una iniciación natural de D (D0) y se genera iterativamente la secuencia de matrices D1, D2, ..., Dn, cuyos elementos tienen el siguiente significado: " D0[i,j] = cij, peso asociado a la arista desde el vértice i al vértice j " D1[i,j] = min (D0[i,j], D0[i,1] + D0[1,j]). Es decir, el menor de los costes entre el anterior camino desde i hasta j y la suma de los costes de caminos desde i hasta 1 y 1 hasta j " D2[i,j] = min (D1[i,j], D1[i,2] + D1[2,j]). Es decir, el menor de los costes entre el anterior camino desde i hasta j y la suma de los costes de caminos desde i hasta 2 y 2 hasta j " Dn[i,j] = min (Dn-1[i,j], Dn-1[i,n] + Dn-1[n,j]). Es decir, el menor de los costes entre el anterior camino desde i hasta j y la suma de los costes de caminos desde i hasta n y n hasta j

Como en el algoritmo de Dijkstra, para cada vértice sería conveniente almacenar el índice del último vértice que ha conseguido que el camino sea mínimo desde vi hasta vj. Para ello, se utiliza una matriz de vértices según el siguiente criterio: • A(vi,vj) = 0 si no hay caminos de vi a vj • A(vi,vj) = vk si vj es accesible desde vi y vk es el sucesor inmediato de vi en el camino mínimo de vi a vj calculado por el algoritmo Algoritmos y Estructuras de Datos II

Tema 4

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

36

El TAD Grafo: caminos mínimos

{ cardinal de V } constante n = ... tipo MatrizDistancias = tabla [n,n] de entero; MatrizCamino = tabla [n,n] de 1..n;

Implementación del algoritmo de Floyd

función Floyd (G: grafo; var A: MatrizCamino): MatrizDistancias; var i,j,k: entero; fvar inicio inicializarCostes (G, D); { almacena en D0 los pesos asociados a las aristas de G. El camino mínimo de un vértice a sí mismo se considera 0 } para i:= 1 hasta n hacer para j:= 1 hasta n hacer A[i,j]:= 0; fpara; fpara; { el índice k indica el subíndice de la matriz D que se está generando} para k:=1 hasta n hacer para i:= 1 hasta n hacer { el índice i indica la fila } { el índice j indica la columna } para j:=1 hasta n hacer si (D[i,k] + D[k,j] < D[i,j]) entonces D[i,j]:= D[i,k] + D[k,j]; A[i,j]:= k; fsi; fpara; fpara; fpara; devuelve D; facción; Algoritmos y Estructuras de Datos II

I.T. en Informática de Gestión/Sistemas

Universidad de Huelva

37