Download El TAD Grafo: árbol de extensión de coste mínimo El TAD Grafo

El TAD Grafo: árbol de extensión de coste mínimo
Tema 4
4.6 Árbol de extensión de coste mínimo
! Problema clásico: encontrar un subgrafo que contenga todos los vértices, que siga siendo
conexo y que el coste total de sus aristas sea mínimo
! Árbol libre:
"
Grafo no dirigido, conexo y acíclico
"
Diferencias con los árboles generales: no tienen raíz y los hijos no están ordenados
! Propiedades:
"
Todo árbol con n vértices tiene n – 1 aristas
"
Si se borra una arista deja de ser conexo, y si se añade una nueva arista, entonces
aparecen ciclos
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
38
El TAD Grafo: árbol de extensión de coste mínimo
Tema 4
! Ej. de aplicación: diseñar una red de transporte (carreteras, ferrocarril, ...) que conecte una
serie de poblaciones construyendo el menor número posible de kilómetros de vía
! Se aplica en grafos no dirigidos, conexos y etiquetados (etiquetas no negativas)
!
Árbol de extensión o de recubrimiento (spanning tree) de coste mínimo:
"
Subconjunto G’ del grafo G
"
Continene todos los vértices de G
"
Es conexo y acíclico
"
No existe otro G’’ tal que la suma de los costes de las aristas de G’’ sea menor que la
suma de los costes de las aristas de G’
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
39
El TAD Grafo: árbol de extensión de coste mínimo
Tema 4
! Ejemplos:
v1
v1
6
5
1
1
5
5
v2
v4
5
v2
v3
6
3
v1
4
2
v4
1
v3
5
6
v5
v2
2
v4
2
v6
4
v3
3
v5
2
3
1
4
3
2
v6
v2
2
v1
4
6
v5
v4
v3
v6
Algoritmos y Estructuras de Datos II
3
v5
I.T. en Informática de Gestión/Sistemas
4
v6
Universidad de Huelva
40
El TAD Grafo: árbol de extensión de coste mínimo
Tema 4
! Estrategias:algoritmos voraces
"
Prim: parte de un vértice cualquiera y va extendiendo el árbol de recubrimiento,
incorporando un nuevo vértice en cada iteración, hasta cubrir todos los vértices del
grafo
"
Kruskal: parte de un bosque de árboles formados por un único vértice cada uno, de
forma que en cada iteración se conectan un par de árboles mediante una arista, hasta
que en el bosque quede un único árbol
4.6.1 Algoritmo de Prim
! Dado un grafo G = (V, A), mantiene dos particiones:
"
U: vértices que se encuentran enlazados por las aristas del árbol que se está
construyendo
"
V – U: resto de vértices
! En cada iteración se incrementa el subconjunto U con un nuevo vértice, hasta que U = V.
! Inicialmente, U contiene un único vértice, que puede ser cualquiera
! En cada paso, se localiza la arista (u, v) de menor coste tal que u ∈ U y v ∈ V – U
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
41
Tema 4
El TAD Grafo: árbol de extensión de coste mínimo
Implementación del algoritmo de Prim
función Prim(G: Grafo): conjunto <arista>;
var
U: conjunto <vértice>;
T: conjunto <arista>;
u, v: vértice;
fvar;
inicio
T := ∅;
U := {cualquier v∈ V};
mientras U <> V hacer
escoger la arista (u, v) de coste mínimo tal que u ∈ U y v ∈ V – U;
T := T ∪ {(u, v)};
U := U ∪ {v}
fmientras;
devuelve T;
ffunción;
Algoritmos y Estructuras de Datos II
Tema 4
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
42
El TAD Grafo: árbol de extensión de coste mínimo
Ejemplo
10
v1
14
v4
v6
9
3
7
v3
v7
4
5
7
v8
2
6
v2
Algoritmos y Estructuras de Datos II
5
v5
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
43
El TAD Grafo: árbol de extensión de coste mínimo
Tema 4
4.6.2 Algoritmo de Kruskal
! Dado un grafo G = (V, A), se comienza con un grafo T = {V, ∅} ⇒ T es un grafo con todos los
nodos de G pero sin ninguna arista
! Durante el algoritmo se mantendrá siempre un bosque de árboles que inicialmente están
formados por un único vértice
! Para añadir las aristas examinamos el conjunto A en orden creciente según su coste:
"
Si la arista seleccionada conecta dos vértices de árboles distintos, se añade al conjunto
de aristas de T puesto que formará parte del árbol de expansión y ambas componentes
se unen en una única componente conexa
"
Si la arista conecta dos vértices que pertenecen al mismo árbol, no se añade para evitar
la aparición de ciclos en el árbol de expansión
! Cuando todos los vértices de T estén en una única componente conexa, habremos encontrado
el árbol de expansión buscado
Algoritmos y Estructuras de Datos II
Tema 4
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
44
El TAD Grafo: árbol de extensión de coste mínimo
Implementación del algoritmo de Kruskal
función Kruskal(G: Grafo): conjunto <arista>;
var
A: lista <arista>;
T: conjunto <arista>;
B: tabla [1..n] de natural; { n es el número de vértices de G}
ai: arista;
i: natural;
fvar;
inicio
A := secuencia de las aristas de G ordenada crecientemente;
para i := 1 hasta n hacer
B[i] := i
fpara;
i := 1;
mientras T.cardinal < n - 1 hacer
ai := A.observa[i];
si B[ai.getOrigen] <> B[ai.getDestino] entonces
T := T ∪ {ai};
fusionar (B, ai.getOrigen, ai.getDestino)
fsi;
i := i +1;
fmientras;
devuelve T;
ffunción;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
45
Tema 4
El TAD Grafo: árbol de extensión de coste mínimo
Ejemplo
10
v1
14
v4
v6
9
3
7
v3
v7
4
5
7
v8
2
6
v2
Algoritmos y Estructuras de Datos II
5
v5
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
46