1
ISIS 1206
ESTRUCTURAS DE
DATOS
CLASE S15-C1
MST
Andrés Moreno Barbosa
ML 341
dar-more@[Link]
Diapositivas adaptadas del material del curso de:
ISIS 1206 - Estructuras de Datos
Robert Sedgewick and Kevin Wayne. 2011. Algorithms (4th ed.). Addison-Wesley Professional.
2
ÁRBOLES DE EXPANSIÓN MÍNIMA
ISIS 1206 - Estructuras de Datos
3
Grafo Ponderado
Un grafo ponderado es un modelo de
grafo donde se asocia pesos o costos
con cada arco.
Dichos grafos son modelos naturales
para muchas aplicaciones.
4
Árboles de Expansión Mínima
• Un árbol de expansión de un grafo es un subgrafo
conectado sin ciclos que incluye todos los vértices.
• Un árbol de expansión mínima (MST) de un grafo
ponderado es un árbol de expansión cuyo peso (la suma
de los pesos de sus arcos) no es mayor que el peso de
cualquier otro árbol de expansión.
5
Árboles de Expansión Mínima
• Un MST de G es un subgrafo T que cumple las siguientes condiciones:
– Conectado
– Acíclico
– Incluye todos los vértices de G
6
Árboles de Expansión Mínima
• Un MST de G es un subgrafo T que cumple las siguientes condiciones:
– Conectado
– Acíclico
– Incluye todos los vértices de G
7
Árboles de Expansión Mínima
• Un MST de G es un subgrafo T que cumple las siguientes condiciones:
– Conectado
– Acíclico
– Incluye todos los vértices de G
8
Árboles de Expansión Mínima
• Un MST de G es un subgrafo T que cumple las siguientes condiciones:
– Conectado
– Acíclico
– Incluye todos los vértices de G
Árboles de Expansión Mínima
Entrada: Grafo no dirigido con pesos (positivos), conectado
Árboles de Expansión Mínima
Entrada: Grafo no dirigido con pesos (positivos), conectado
Salida: MST de peso mínimo (mínima suma posible de arcos)
Aplicaciones
Aplicaciones
13
Aplicaciones
• Análisis de clusters. • Verificación en tiempo real.
• Máximos caminos de cuello de • Modelo de ubicación de interacciones de
botella. partículas en flujos de fluidos turbulentos.
• Códigos LDPC para corrección de • Protocolos de autoconfiguración para
errores. puenteo de Ethernet para evitar ciclos en
• Encontrar redes de carreteras en una red.
imágenes satelitales y aéreas. • Algoritmos de aproximación para
• Reducir el almacenamiento de datos problemas NP-hard.
en la secuenciación de aminoácidos • Diseño de redes (comunicación, eléctrico,
en una proteína. hidráulico, computadores, vías).
ISIS 1206 - Estructuras de Datos
14
GREEDY ALGORITHM
ISIS 1206 - Estructuras de Datos
15
Suposiciones
• El grafo está conectado.
– Si un grafo no está conectado, podemos adaptar nuestros algoritmos para
calcular los MST de cada uno de sus componentes conectados,
conocidos colectivamente como un bosque de extensión mínima
• Los pesos de los arcos no son necesariamente distancias.
– Los pesos pueden representar tiempo o costo o una variable
completamente diferente y no necesitan ser proporcionales a una
distancia en absoluto.
16
Suposiciones
• Los pesos del arco pueden ser cero o negativos.
– La definición permite que el algoritmo se aplique a los grafos que pueden
tener pesos de arco negativos o cero.
• Los pesos de los arcos son todos diferentes.
– Si los arcos pueden tener pesos iguales, el árbol de expansión mínimo
puede no ser único.
– Esta suposición no es restrictiva porque los algoritmos funcionan sin
modificaciones en presencia de pesos iguales.
Simplificación
• Si el grafo es conectado y si sus pesos son distintos
– Existe un único MST y su costo total es único
18
Principios Subyacentes de los Árboles
• Agregar un arco que conecta
dos vértices en un árbol crea
un ciclo único.
• Al eliminar un arco de un
árbol, se divide en dos
subárboles separados.
19
Propiedad de Corte
• Esta propiedad, tiene que ver con identificar los arcos que
deben estar en el MST de un grafo ponderado dado.
• La propiedad de corte divide los vértices en dos conjuntos
y examina los arcos que cruzan la división.
20
Propiedad de Corte
• Un corte de un grafo es una división de sus vértices en
dos conjuntos disjuntos no vacíos.
• Un arco de cruce de un corte es un arco que conecta un
vértice en un conjunto con un vértice en el otro.
21
Propiedad de Corte
22
Propiedad de Corte
• Para cualquier corte, el arco de cruce con el mínimo peso es
parte del MST del grafo.
• Suponga que 𝑒 es un arco de cruce con peso mínimo y no esta
en el MST
23
Propiedad de Corte
Suponga que 𝑒 es un arco de cruce con
peso mínimo y no esta en el MST
• Si se añade 𝑒 se crea un ciclo y deja de ser
un MST
• Debe existir otro arco 𝑓 que sea un arco de
cruce
• Quitar 𝑓 y añadir 𝑒 sigue siendo un MST
• Contradicción: Como el peso de e es
menor al de f, el MST con f no es un MST y
tiene que incluir a e
24
Greedy algorithm
• Todos los arcos comienzan coloreados en gris
• Encuentre un corte que no tenga arcos de cruce negros,
coloree el arco de cruce con peso mínimo de negro.
• Repita hasta colorear V-1 arcos, los arcos coloreados
conforman un MST
25
Greedy algorithm
Greedy algorithm
¿Por qué funciona?
• Todos los arcos coloreados pertenecen al MST (por propiedad de corte)
• El MST solo se conecta al colorear V-1 arcos
Greedy algorithm
¿Qué pasa si los pesos no son únicos?
• Algoritmo encuentra MST, pero puede no ser único el MST
Greedy algorithm
¿Qué pasa si el grafo no es conectado?
• Algoritmo encuentra el MST de los componentes conectados
Implementaciones eficientes
• ¿Cómo encontrar un corte?
• ¿Cómo encontrar el arco con el costo mínimo para el
corte?
– Kruskal
– Prim
30
API ARCO CON PESO
ISIS 1206 - Estructuras de Datos
31
API de arcos con peso
32
API de arcos con peso
public class Edge implements Comparable<Edge>
{
private final int v; // one vertex
private final int w; // the other vertex
private final double weight; // edge weight
public Edge(int v, int w, double weight)
{
this.v = v;
this.w = w;
[Link] = weight;
}
public double weight()
{ return weight; }
public int either()
{ return v; }
33
API de arcos con peso
public int other(int vertex)
{
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new RuntimeException("Inconsistent edge");
}
public int compareTo(Edge that)
{
if ([Link]() < [Link]()) return -1;
else if ([Link]() > [Link]()) return +1;
else return 0;
}
public String toString()
{ return [Link]("%d-%d %.2f", v, w, weight); }
}
34
API de grafos con peso
35
API de grafos con peso
36
API de grafos con peso
public class EdgeWeightedGraph
{
private final int V; // number of vertices
private int E; // number of edges
private Bag<Edge>[] adj; // adjacency lists
public EdgeWeightedGraph(int V)
{
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<Edge>();
}
37
API de grafos con peso
public int V() { return V; }
public int E() { return E; }
public void addEdge(Edge e)
{
int v = [Link](), w = [Link](v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public Iterable<Edge> adj(int v)
{ return adj[v]; }
}
38
MST API
39
MST API
public static void main(String[] args)
{
In in = new In(args[0]);
EdgeWeightedGraph G;
G = new EdgeWeightedGraph(in);
MST mst = new MST(G);
for (Edge e : [Link]())
[Link](e);
[Link]([Link]());
}
40
41
ALGORITMO DE KRUSKAL
ISIS 1206 - Estructuras de Datos
42
Algoritmo de Kruskal
• Este algoritmo procesa los arcos en orden de sus valores de peso
(del más pequeño al más grande), tomando para el MST
(pintando de negro) cada arco que no forma un ciclo con los
arcos agregados previamente, deteniéndolo después de agregar
V-1 arcos.
• Los arcos negros forman un bosque de árboles que evoluciona
gradualmente en un único árbol, el MST.
Kruskal
• Ordenar los arcos en orden ascendente por peso
– Colorear arco si no forma un ciclo
[Link]
Algoritmo de Kruskal
¿Por qué funciona?
• Cuando se marca un arco se crea un corte con un arco mínimo
– Si se genera un ciclo quiere decir que ya había un arco uniendo los
árboles con un arco de costo menor
Algoritmo de Kruskal
Complejidad de encontrar un ciclo
• DFS – Complejidad V en el peor caso
• Mantener un conjunto por cada componente
conectado de T , no del grafo G
– Si el arco une vértices del mismo componente
conectado, se crea un ciclo
– Si el arco une vértices de componentes conectados
diferentes, se vuelven un solo componente conectado
Union Find en MST
By Shiyu Ji - Own work, CC BY-SA 4.0,
Kruskal
Kruskal
• Java
Estructura para guardar
componentes
conectados de T
Kruskal
• Java
Estructura para guardar
componentes
conectados de T
Kruskal
• Java
Estructura para guardar
componentes
conectados de T
Kruskal
• Java
Kruskal
• Análisis de complejidad
53
Implementación
public class KruskalMST
{
private Queue<Edge> mst;
public KruskalMST(EdgeWeightedGraph G)
{
mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>([Link]());
UF uf = new UF(G.V());
while (![Link]() && [Link]() < G.V()-1)
{
Edge e = [Link](); // Get min weight edge on pq
int v = [Link](), w = [Link](v); // and its vertices.
if ([Link](v, w)) continue; // Ignore ineligible edges.
[Link](v, w); // Merge components.
[Link](e); // Add edge to mst.
}
}
}
54
Algoritmo de Kruskal - Complejidad
El algoritmo de Kruskal calcula MST en tiempo proporcional
a 𝐸 ∙ log 𝐸 (en el peor de los casos).
55
ALGORITMO DE PRIM
ISIS 1206 - Estructuras de Datos
Prim
• Comenzar desde un vértice arbitrario (0) y crecer el
árbol
– Listar los arcos con solo extremo en T
– Añadir a T el arco con menor costo
– Repetir V-1 veces
[Link]
Algoritmo de Prim
¿Por qué funciona?
• Cuando se marca un arco se crea un corte con un arco mínimo
– Si se genera un ciclo quiere decir que ya había un arco uniendo los
árboles con un arco de costo menor
Algoritmo de Prim
¿Complejidad de encontrar el arco con un extremo en T con menor
costo?
• log E -> Colas de prioridad
Lazy implementation - Prim
• ¿Complejidad de encontrar el arco con un extremo en
T con menor costo?
– Colas de prioridad: Llave: Arco, Valor: Peso
• Sacar el mínimo de la cola
• Descartar si ambos extremos están en T
• Si no, marcar arco y encolar los arcos adyacentes al nuevo vértice
que tengan un extremo que no esta en T
Lazy implementation - Prim
Lazy implementation - Prim
Lazy implementation - Prim
Lazy implementation - Prim
Lazy implementation - Prim
Lazy implementation - Prim
Lazy implementation - Prim
67
PRIM - Lazy Implementation
public class LazyPrimMST
{
private boolean[] marked; // MST vertices
private Queue<Edge> mst; // MST edges
private MinPQ<Edge> pq; // crossing (and ineligible) edges
public LazyPrimMST(EdgeWeightedGraph G)
{
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
mst = new Queue<Edge>();
visit(G, 0); // assumes G is connected
while (![Link]()) {
Edge e = [Link](); // Get lowest-weight
int v = [Link](), w = [Link](v); // edge from pq.
if (marked[v] && marked[w]) continue; // Skip if ineligible.
[Link](e); // Add edge to tree.
if (!marked[v]) visit(G, v); // Add vertex to tree
if (!marked[w]) visit(G, w); // (either v or w).
}
}
68
PRIM - Lazy Implementation
private void visit(EdgeWeightedGraph G, int v)
{ // Mark v and add to pq all edges from v to unmarked vertices.
marked[v] = true;
for (Edge e : [Link](v))
if (!marked[[Link](v)]) [Link](e);
}
public Iterable<Edge> edges()
{
return mst;
}
}
69
Algoritmo Lazy Prim - Complejidad
El algoritmo Lazy Prim calcula el MST en tiempo proporcional a 𝐸 ∙ log 𝐸 y
espacio adicional proporcional a 𝐸 (en el peor de los casos).
Eager implementation Prim
• Mantener una cola de prioridad de
vértices conectados a T
– Sacar de la cola el vértice mínimo y
asociarlo a T
– Realizar actualización de la cola de
prioridad
• Para cada arco del nuevo vértice alcanzado
por T:
– Si el otro extremo ya esta en T, ignorar
– Añadirlo a la cola de prioridad si no existe
– Cambiar el peso de los arcos en la cola de prioridad
si resulta siendo menor
Cola de prioridad indexada
• Permite asignar un índice a cada llave
• Permite decrementar el valor de una llave
Cola de prioridad indexada