PDF de programación - Estructuras de datos y algoritmos 4. Grafos y caminos

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas, y pilas
6. Implementación de mapas, árboles, y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

4/nov/09

1

UNIVERSIDAD
DE CANTABRIA

4. Grafos y Caminos
• 4.1. Concepto de grafo
• 4.2. Definiciones
• 4.3. La interfaz de las aristas
• 4.4. La interfaz de los grafos
• 4.5. Cálculo de caminos mínimos sin pesos
• 4.6. Cálculo de caminos mínimos con pesos positivos
• 4.7. Cálculo de caminos mínimos con pesos negativos
• 4.8. Cálculo de caminos en grafos acíclicos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

2

4.1 Grafos
Un grafo es una estructura de datos que almacena datos de dos
tipos:
• vértices o nudos, con un valor almacenado
• aristas o arcos: cada una conecta a un vértice con otro, y puede

tener un valor almacenado
- una arista es un par de vértices (v,w)
- si el par está ordenado, se dice que el grafo es dirigido o que es un

UNIVERSIDAD
DE CANTABRIA

digrafo

A

19
C

12

87

10

B
23
D

11

43

E

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

3

Notas:

UNIVERSIDAD
DE CANTABRIA

Los grafos, constituyen estructuras de datos en las que se pueden expresar relaciones de conexión entre
diversos elementos denominados vértices. Cada conexión se representa por un dato llamado arista

Los grafos tienen gran cantidad de aplicaciones; por ejemplo:

• Representación de circuitos electrónicos analógicos y digitales
• Representación de caminos o rutas de transporte entre localidades
• Representación de redes de computadores.

Uno de los problemas más importantes en los grafos es el de encontrar el camino de coste mínimo.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

4

4.2. Definiciones
• Adyacente: se dice que w es adyacente a v si existe la arista

(v,w)
- en un grafo dirigido, no es lo mismo que v sea adyacente a w que

UNIVERSIDAD
DE CANTABRIA

• Camino: secuencia de vértices tales que cada uno es adyacente

al revés

al anterior

• Peso o coste: las aristas pueden contener datos y uno de ellos

puede ser el coste o peso asociado a esa arista.
- se usa para determinar el coste de recorrer el camino

• Longitud del camino: nº de aristas que tiene
• Coste de un camino: la suma de los pesos de sus aristas
• Camino simple: es aquel en que todos los vértices son distintos,

excepto quizás el primero y el último

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

5

Definiciones (cont.)
• Ciclo: es un camino de longitud al menos 1 que empieza y acaba

UNIVERSIDAD
DE CANTABRIA

en el mismo vértice

• Grafo dirigido acíclico: es un grafo dirigido sin ciclos
• Grafo denso: es aquel que tiene un gran número de aristas

- cercano al número de vértices, V, al cuadrado

• Grafo disperso: es aquel en que el número de aristas E es
pequeño E<<V2
- es el tipo de grafo más habitual
-

intentaremos optimizar las operaciones del grafo para este caso

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

6

4.3. La interfaz de las aristas
Los vértices del grafo se suelen numerar para trabajar con ellos
más cómodamente
• disponen de un identificador entero
Las aristas son objetos que contienen
• el identificador del vértice origen

- en ocasiones este dato no se almacena, pues se averigua a partir

UNIVERSIDAD
DE CANTABRIA

del grafo

• el identificador del vértice destino
• un contenido

- el peso, en el caso de los grafos con pesos
- opcionalmente, más datos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

7

4.3. La interfaz de las aristas
Operaciones

UNIVERSIDAD
DE CANTABRIA

operación
constructor
idOrigen
idDestino
contenido

argumentos

retorna

errores

idOrigen, idDestino, peso, ... Arista
entero
entero
Contenido

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

8

UNIVERSIDAD
DE CANTABRIA

La clase Arista
package adts;
public class Arista<A>
{
public Arista (int origen, int destino,
A contenido) {...}
public int destino() {...}
public int origen() {...}
public A contenido() {...}
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

9

4.4. La interfaz abstracta de los
grafos
Operaciones del grafo:

UNIVERSIDAD
DE CANTABRIA

argumentos

retorna

errores

Grafo

elemOrigen, elemDestino, contArista
elemento
entero
entero

operación
constructor
nuevaArista
idVertice
contenido
listaAristas
numVertices
numAristas
El elemento que se guarda en los vértices debe implementar
• hashCode() e equals()

entero
Elemento
List<Arista>
entero
entero

NoExiste
IdIncorrecto
IdIncorrecto

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

10

Notas:

UNIVERSIDAD
DE CANTABRIA

• constructor: Crea el grafo vacío
• nuevaArista: Inserta una nueva arista con peso a partir de las descripciones de sus vértices. Si los
vértices son nuevos, los añade al grafo
• idVertice: Retorna el identificador del vértice indicado. Lanza NoExiste si el vértice no pertenece al
grafo
• contenido: Retorna el contenido del vértice cuyo identificador se indica. Lanza IdIncorrecto si ese
identificador no pertenece al grafo
• listaAristas: Retorna la lista de aristas del vértice de identificador idVertice. Lanza IdIncorrecto
si ese identificador no pertenece al grafo

• numVertices: Retorna el número de vértices
• numAristas: Retorna el número de aristas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

11

UNIVERSIDAD
DE CANTABRIA

La interfaz Java de los grafos
package adts;
import java.util.*;
public interface Grafo<V,A>
{
Arista nuevaArista (V vertice1, V vertice2,
A contenidoArista);
int idVertice(V vertice)
throws NoExiste;
V contenido(int idVertice)
throws IdIncorrecto;
List<Arista<A>> listaAristas(int idVertice)
throws IdIncorrecto;
int numVertices();
int numAristas();
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

12

Ejemplo con grafos
1. Escribir un método para recorrer todos los arcos de un grafo y
mostrarlos en la pantalla
2. Escribir un método al que se le pase un camino, como una lista
de valores de vértices, y nos calcule su coste o peso total

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

13

4.5. Cálculo de caminos mínimos sin
pesos
El problema del cálculo del camino mínimo se define como
• Encontrar el camino de menor coste desde un vértice dado

Origen (O) hasta cualquier otro vértice del grafo

UNIVERSIDAD
DE CANTABRIA

• Cuando no hay pesos, el coste es la longitud del camino
Tiene muchas aplicaciones. Por ejemplo:
• ruta más rápida para un trasporte
• camino más corto para un e-mail en una red de computadores

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

14

Resolución del problema
Resolveremos el problema calculando los caminos mínimos a
otros vértices
• el camino desde O a sí mismo es de longitud 0
• procesar O: buscamos los vértices cuyo camino mínimo desde

UNIVERSIDAD
DE CANTABRIA

O es de longitud 1
- son los vértices adyacentes a O

• procesar vértices adyacentes a O: buscamos los vértices cuyo

camino mínimo desde O es de longitud 2
- son los vértices aún no visitados que son adyacentes a los vértices

del paso anterior

• en el paso i, buscamos los vértices cuyo camino mínimo desde

O es de longitud i
- vértices aún no visitados adyacentes a los del paso anterior

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

15

Resolución del problema
En este algoritmo se garantiza que la primera vez que se visita un
vértice se ha hecho por el camino mínimo
Organización de los datos
• Necesitamos guardar en cada vértice el hecho de que lo hemos

UNIVERSIDAD
DE CANTABRIA

visitado o no

• Para recordar el camino, podemos anotar en cada vértice cuál es

el vértice desde el que procede el camino

• Necesitamos almacenar el conjunto de vértices a procesar

- podemos usar una cola

Como cada arista se recorre como máximo una vez, el coste de
este algoritmo en el peor caso es O(E), siendo E el número de
aristas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

16

Ejemplo
En el grafo siguiente se han anotado los sucesivos valores de
longitud del camino y vértice anterior, suponiendo el origen= V2

UNIVERSIDAD
DE CANTABRIA

1,V2

V0

2,V0

V1

0,-

V2

2,V0
V3

V4

3,V1

V5
1,V2

V6

3,V3

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

17

UNIVERSIDAD
DE CANTABRIA

Pseudocódigo del camino mínimo
método caminoMinimoSinPesos (Grafo g,
idVertice origen, destino)
retorna Camino
// inicializaciones
Cola<idVertice> procesar:= nueva Cola vacía;
idVertice anterior[]:= nuevo array[numVertices]
boolean visitado[]:= nuevo array[numVertices]=
false para todas sus casillas

procesar.inserta(origen)
visitado[origen]:=true
anterior[origen]:=-1 // para indicar que no tiene

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

4/nov/09

18

UNIVERSIDAD
DE CANTABRIA

Pseudocódigo del camino mínimo (cont.)
mientras procesar no esta vacío hacer
idVertice v:=procesar.extraer()
Lista adj:=g.listaAristas(v)
para cada arista a de adj hacer
idVertice dest:=a.destino;
si no visitado[dest] entonces
anterior[dest]:=v
si dest==destino entonces
retorn