PDF de programación - Tema 22: Algoritmos sobre grafos - Informática (2016–17)

Tema 22: Algoritmos sobre grafos

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 22: Algoritmos sobre grafos

Tema 22: Algoritmos sobre grafos
1. El TAD de los grafos

Definiciones y terminología sobre grafos
Signatura del TAD de los grafos
Implementación de los grafos como vectores de adyacencia
Implementación de los grafos como matrices de adyacencia

2. Recorridos en profundidad y en anchura

Recorrido en profundidad
Recorrido en anchura

3. Árboles de expansión mínimos

Árboles de expansión mínimos
El algoritmo de Kruskal
El algoritmo de Prim

2 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Definiciones y terminología sobre grafos

Tema 22: Algoritmos sobre grafos

1. El TAD de los grafos

Definiciones y terminología sobre grafos
Signatura del TAD de los grafos
Implementación de los grafos como vectores de adyacencia
Implementación de los grafos como matrices de adyacencia

2. Recorridos en profundidad y en anchura

3. Árboles de expansión mínimos

3 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Definiciones y terminología sobre grafos

Definiciones y terminología sobre grafos

Un grafo G es un par (V , A) donde V es el conjunto de los

vértices (o nodos) y A el de las aristas.

Una arista del grafo es un par de vértices.
Un arco es una arista dirigida.
|V| es el número de vértices.
|A| es el número de aristas.
Un vértice v es adjacente a v0 si vv0 es una arista del grafo.
Un grafo ponderado es un grafo cuyas aristas tienen un peso.

4 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Signatura del TAD de los grafos

Tema 22: Algoritmos sobre grafos

1. El TAD de los grafos

Definiciones y terminología sobre grafos
Signatura del TAD de los grafos
Implementación de los grafos como vectores de adyacencia
Implementación de los grafos como matrices de adyacencia

2. Recorridos en profundidad y en anchura

3. Árboles de expansión mínimos

5 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Signatura del TAD de los grafos

Signatura del TAD de los grafos

creaGrafo

:: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] ->

Grafo v p

:: (Ix v,Num p) => (Grafo v p) -> Bool

dirigido
adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos
aristas
aristaEn
peso

:: (Ix v,Num p) => (Grafo v p) -> [v]
:: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
:: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
:: (Ix v,Num p) => v -> v -> (Grafo v p) -> p

6 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Signatura del TAD de los grafos

Descripción de la signatura del TAD de grafos

(creaGrafo o cs as) es un grafo (dirigido o no, según el valor
de o), con el par de cotas cs y listas de aristas as (cada arista es
un trío formado por los dos vértices y su peso).
Ver un ejemplo en la siguiente transparencia.

(dirigido g) se verifica si g es dirigido.
(nodos g) es la lista de todos los nodos del grafo g.
(aristas g) es la lista de las aristas del grafo g.
(adyacentes g v) es la lista de los vértices adyacentes al nodo

v en el grafo g.

(aristaEn g a) se verifica si a es una arista del grafo g.
(peso v1 v2 g) es el peso de la arista que une los vértices v1 y

v2 en el grafo g.

7 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Signatura del TAD de los grafos

Ejemplo de creación de grafos.

creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]

crea el grafo
12

\

5

1 -------- 2
| \78
/|
32/ |
| \
|
|
/
|55
34|
/
|
|
\ |
| /44
| /
93\|
3 -------- 4

\

61

8 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Tema 22: Algoritmos sobre grafos

1. El TAD de los grafos

Definiciones y terminología sobre grafos
Signatura del TAD de los grafos
Implementación de los grafos como vectores de adyacencia
Implementación de los grafos como matrices de adyacencia

2. Recorridos en profundidad y en anchura

3. Árboles de expansión mínimos

9 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

Cabecera del módulo:

module GrafoConVectorDeAdyacencia

(Orientacion (..),
Grafo,
creaGrafo, -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] ->

--
-- (Ix v,Num p) => (Grafo v p) -> Bool

Grafo v p

dirigido,
adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos,
aristas,
aristaEn,
peso
) where

-- (Ix v,Num p) => (Grafo v p) -> [v]
-- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
-- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
-- (Ix v,Num p) => v -> v -> (Grafo v p) -> p

Librerías auxiliares.

import Data.Array

10 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

Orientacion es D (dirigida) ó ND (no dirigida).

data Orientacion = D | ND

deriving (Eq, Show)

(Grafo v p) es un grafo con vértices de tipo v y pesos de tipo

p.

data Grafo v p = G Orientacion (Array v [(v,p)])

deriving (Eq, Show)

11 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(creaGrafo o cs as) es un grafo (dirigido o no según el valor de o),

con el par de cotas cs y listas de aristas as (cada arista es un trío
formado por los dos vértices y su peso). Ver un ejemplo a continuación.

creaGrafo :: (Ix v, Num p) =>

Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p

creaGrafo D cs vs =
G ND (accumArray

(\xs x -> xs ++ [x]) [] cs
[(x1,(x2,p)) | (x1,x2,p) <- vs])

creaGrafo ND cs vs =
G D (accumArray

(\xs x -> xs ++ [x]) [] cs
([(x2,(x1,p)) | (x1,x2,p) <- vs, x1 /= x2] ++
[(x1,(x2,p)) | (x1,x2,p) <- vs]))

12 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(creaGrafo o cs as) es un grafo (dirigido o no según el valor de o),

con el par de cotas cs y listas de aristas as (cada arista es un trío
formado por los dos vértices y su peso). Ver un ejemplo a continuación.

creaGrafo :: (Ix v, Num p) =>

Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p

creaGrafo D cs vs =
G ND (accumArray

(\xs x -> xs ++ [x]) [] cs
[(x1,(x2,p)) | (x1,x2,p) <- vs])

creaGrafo ND cs vs =
G D (accumArray

(\xs x -> xs ++ [x]) [] cs
([(x2,(x1,p)) | (x1,x2,p) <- vs, x1 /= x2] ++
[(x1,(x2,p)) | (x1,x2,p) <- vs]))

12 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

ejGrafoND es el grafo que de la página 8. Por ejemplo,

ghci> ejGrafoND
G ND array (1,5) [(1,[(2,12),(3,34),(5,78)]),
(2,[(1,12),(4,55),(5,32)]),
(3,[(1,34),(4,61),(5,44)]),
(4,[(2,55),(3,61),(5,93)]),
(5,[(1,78),(2,32),(3,44),(4,93)])])

ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]

13 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

ejGrafoD es el mismo grafo que ejGrafoND pero orientando las

aristas de menor a mayor. Por ejemplo,
ghci> ejGrafoD
G D array (1,5) [(1,[(2,12),(3,34),(5,78)]),

(2,[(4,55),(5,32)]),
(3,[(4,61),(5,44)]),
(4,[(5,93)]),
(5,[])])

ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]

14 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(dirigido g) se verifica si g es dirigido. Por ejemplo,

dirigido ejGrafoD
dirigido ejGrafoND

==
True
== False

dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool
dirigido (G o _) = o == D

(adyacentes g v) es la lista de los vértices adyacentes al nodo

v en el grafo g. Por ejemplo,
adyacentes ejGrafoND 4 ==
adyacentes ejGrafoD
4 ==

[2,3,5]
[5]

adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
adyacentes (G _ g) v = map fst (g!v)

15 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(dirigido g) se verifica si g es dirigido. Por ejemplo,

dirigido ejGrafoD
dirigido ejGrafoND

==
True
== False

dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool
dirigido (G o _) = o == D

(adyacentes g v) es la lista de los vértices adyacentes al nodo

v en el grafo g. Por ejemplo,
adyacentes ejGrafoND 4 ==
adyacentes ejGrafoD
4 ==

[2,3,5]
[5]

adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
adyacentes (G _ g) v = map fst (g!v)

15 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,

nodos ejGrafoND
nodos ejGrafoD

== [1,2,3,4,5]
== [1,2,3,4,5]

nodos :: (Ix v,Num p) => (Grafo v p) -> [v]
nodos (G _ g) = indices g

(peso v1 v2 g) es el peso de la arista que une los vértices v1 y

v2 en el grafo g. Por ejemplo,
peso 1 5 ejGrafoND ==
peso 1 5 ejGrafoD

78
== 78

peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
peso x y (G _ g) = head [c | (a,c) <- g!x , a == y]

16 / 52

IM Tema 22: Algoritmos sobre grafos

El TAD de los grafos

Implementación de los grafos como vectores de adyacencia

Los grafos como vectores de adyacencia

(nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,

nodos ejGrafoND
nodos ejGrafoD

== [1,2,3,4,