PDF de programación - Programa de teoría Parte I. Estructuras de Datos

Programa de teoría

Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 4. Grafos.

1

PARTE I: ESTRUCTURAS DE DATOS

Tema 4. Grafos.
4.1. Introducción, notación y definiciones.
4.2. Representación de grafos.
4.3. Problemas y algoritmos sobre grafos.

4.3.1. Recorridos sobre grafos.
4.3.2. Árboles de expansión mínimos.
4.3.3. Problemas de caminos mínimos.
4.3.4. Algoritmos sobre grafos dirigidos.
4.3.5. Algoritmos sobre grafos no dirigidos.
4.3.6. Otros problemas con grafos.

A.E.D.

Tema 4. Grafos.

2

1

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo de carreteras entre ciudades.

Coruña
1
7
1

Vigo

Oviedo

45
5

356

304

280

5
9
3

Valladolid

1

9

3

Bilbao

3

2

3 2 5

3

0

4

5
3
3

Jaén
2 4 2

256

Badajoz

Sevilla
125

Cádiz

4

Zaragoza
296

Gerona

100
Barcelona

Madrid

2

5

1

Albacete

1

5

349

Valencia

1

9

1

1
4
2

0

Murcia

9

9

8

7

2

Granada

A.E.D.

Tema 4. Grafos.

3

4.1.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 4. Grafos.

4

2

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo de transiciones de un AFD.

b

0

inicio

b

b

a

1

2

a

a

a

b

3

A.E.D.

Tema 4. Grafos.

5

4.1.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 4. Grafos.

6

3

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo de planificación de tareas.

Licencia
de obras

6

Aplanar
terreno

4

Comprar
piedras

2

Hacer
camino

3

Cincelar
piedras

8

Pintar
pirámide

3

Colocar
piedras

9

A.E.D.

Tema 4. Grafos.

7

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo de planificación de tareas.

Problemas

• ¿En cuanto tiempo, como mínimo, se puede

construir la pirámide?

• ¿Cuándo debe empezar cada tarea en la

planificación óptima?

• ¿Qué tareas son más críticas (es decir, no pueden

sufrir retrasos)?

• ¿Cuánta gente necesitamos para acabar las

obras?

A.E.D.

Tema 4. Grafos.

8

4

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo asociado a un dibujo de líneas.

Escena

Modelo 1

22

55

11

33

66

Modelo 2

aa

bb

cc

dd

44

77

ee

A.E.D.

Tema 4. Grafos.

9

4.1.1. Ejemplos de grafos.

• Ejemplo: Grafo 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 4. Grafos.

10

5

Coruña
1
17

Vigo

4.1.1. Ejemplos de grafos.

Oviedo

304

Bilbao

455

356

280

5
9
3

Valladolid

1

9

3

3 2 5

3

2

4

Zaragoza
296

Gerona

100
Barcelona

inicio

b

0

a

a

b

b

a

1

2

a

b

3

4 0 3

5
3
3

Jaén
2 4 2
256

Badajoz

Sevilla
125

Cádiz

B | 4B | 4

D | 3D | 3

349

Madrid

2

5

1

Albacete

1

5

Valencia

1
9
1
241

9

9

8

7

2

0

Murcia

Granada

A | 6A | 6

C | 2C | 2
E | 8E | 8

F | 9F | 9

+

G | 3G | 3

A.E.D.

Tema 4. Grafos.

11

4.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
• Grafo no dirigido.

Las aristas no están ordenadas:

(v, w) = (w, v)

• Grafos dirigidos (o digrafos).

Las aristas son pares ordenados:
<v, w> ≠ <w, v>
<v, w> ⇒ w = cabeza de la arista, v = cola.

vv

vv

A.E.D.

Tema 4. Grafos.

ww

ww

12

6

4.1.2. 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 4. Grafos.

13

4.1.2. 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 4. Grafos.

14

7

4.1.2. 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 4. Grafos.

15

4.1.2. 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 4. Grafos.

16

8

4.1.3. 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

17

A.E.D.

Tema 4. Grafos.

4.2. Representación de grafos.

• Representación de grafos:

– Representación del conjunto de nodos, V.
– Representación del conjunto de aristas, A.

11

44

33

22

55

• Ojo: las aristas son relaciones “muchos a

muchos” entre nodos...

A.E.D.

Tema 4. Grafos.

18

9

4.2. Representación de grafos.

• Representación del conjunto de aristas, A.

– Mediante matrices de adyacencia.

2
T

3
T
T

1M
1
2
3
4
5

T

5

T
T

4

T

T

– Mediante listas de adyacencia.

33

22

55

11

44

5

1
2
3
4
5

+

3
5
4

2
3
1

4

A.E.D.

Tema 4. Grafos.

19

4.2.1. 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

11

44

33

22

55

1M
1
T
2
T
3
4
5

T

2
T
T
T

T

3

T

T

5

T

T

4
T

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 4. Grafos.

20

10

4.2.1. 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.

3

11

22

2

4

0

33

3

2
3

4

4

2
2

1M
1
2
3
4

0

2

44

• ¿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 4. Grafos.

21

4.2.1. 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 4. Grafos.

22

11

4.2.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.

11

44

33

22

55

1
2
3
4
5

1
1
2
1
2

2
2
4
3
4

5

4
3

5

• Grafo no dirigido Las aristas están repetidas.
• Resultado: también se desperdicia memoria.

A.E.D.

Tema 4. Grafos.

23

4.2.2. Listas de adyacencia.

• Grafos etiquetados:

tipo GrafoEtiq[E]= array [1..n] de Lista[Nodo,E]

11
a
22

d

c

a

33

b

44

1
2
3
4

2 a
4 b
1 a

2 c

4 d

• ¿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 4. Grafos.

24

12

4.2.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 4. Grafos.

25

4.2.3. Listas múltiples de adyacencia.
• Alternativa: Usar estructuras de listas múltiples.

– Lista de arcos

de salida.

– Lista de arcos

de entrada

a

1

d

array de
nodos
1
2
3
lista_ent

a
b

lista_sal

2

e

b
c

3

c

registros
de aristas

d
e

t

n
e
_
g
s

i

l

r
o
a
v

l

a
s
_
g
s

i

A.E.D.

Tema 4. Grafos.

26

13

4.3. Problemas y algoritmos sobre grafos.

4.3.1. Recorridos sobre grafos.
4.3.2. Árboles de expansión mínimos.
4.3.3. Problemas de caminos mínimos.
4.3.4. Algoritmos sobre grafos dirigidos.
4.3.5. Algoritmos sobre graf