Algoritmo de Prim

Teoria dos Grafos
Aula 11
Aula passada
Aula de hoje
Grafos com pesos
MST
Dijkstra
Algoritmos de Prim e Kruskal
Implementação
Fila de prioridades e Propriedades da MST
Heap
Dijkstra (o próprio)
Projetando uma Rede
$$$
$$
$$$
$
$
$$
$$
$$
$
$$$$
$$
Conjunto de localidades
(ex. cidades)
Custo para conectá-los
diretamente (ex.
construir estradas)
Garantir a conectividade
de qualquer lugar, chegamos a qualquer outro
Problema: Como conectar as localidades
de forma a minimizar o custo total?
Figueiredo – 2010
Projetando uma Rede
$$$
Abstração via grafos
Vértices: localidades
Arestas com pesos: custo
de conexão direta entre
localidades
$$
$$$
$
$
$$
$$
$$
$
$$
$$$$
Como será a “cara” do resultado?
Subgrafo de G, Árvore, Árvore geradora!
Qualquer árvore?
Não!
Árvore Geradora de Custo Mínimo!
Figueiredo – 2010
MST
Minimum Spanning Tree (MST)
árvore geradora de custo mínimo
Exemplo
1
b
3
4
2
a
5
d
5
MST?
c
1
e
1
b
3
4
2
a
f
c
2
d
1
e
f
Custo desta MST? 11
MST é única?
Figueiredo – 2010
Descobrindo a MST
Problema: Obter a MST de um grafo
Grafo com pesos
idênticos?
BFS to the rescue!
qualquer árvore geradora tem custo mínimo
Grafo com pesos diferentes?
Idéias?
Figueiredo – 2010
Descobrindo a MST – Idéias I
Modificar BFS
BFS constrói uma árvore geradora
Dado vértice inicial s
Construir árvore geradora mínima
Expandir “fronteira” na direção correta
Qual é a “direção” correta?
Direção de menor custo
Adicionar vértice que aumenta o
custo total o menos possível
Figueiredo – 2010
Descobrindo a MST – Idéias I
Dado G=(V, E)
Construir MST, T=(S, E')
Inicialmente S e E' estão vazios
Selecionar s, vértice inicial
Adicionar vértices em T na ordem mais
barata possível
próximo vértice aumenta custo total o mínimo
possível
Algoritmo de Prim
Muito parecido com qual algoritmo?
Figueiredo – 2010
Algoritmo de Prim
Idéia: crescer T de forma mais barata
possível
1
b
c
Exemplo
3
4
2
s a
5
b
b
4
s a
a
5
d
1
e
1
2
f
1
b
c
c
4
4
d
a
e
a
f
2
d
e
...
f
Figueiredo – 2010
Algoritmo de Prim
Como tornar a idéia em algoritmo
(eficiente)?
adicionar o vértice que aumenta o custo
o menos possível
Idéias:
Manter um conjunto de vértices da árvore
Manter custo para adicionar cada vértice até
o momento
Adicionar o vértice de menor custo
Atualizar custos
Figueiredo – 2010
Algoritmo de Prim
1.Prim(G, o)
2.Para cada vértice v
3.
custo[v] = infinito
4.Define conjunto S = 0 // vazio
5.custo[o] = 0
6.Enquanto S != V
7.
Selecione u em V-S, tal que custo[u] é mínimo
8.
Adicione u em S
9.
Para cada vizinho v de u faça
10.
Se custo[v] > w((u,v)) então
11.
custo[v] = w((u,v))
Como o algoritmo executa?
Figueiredo – 2010
Executando o Algoritmo
1
a
b
4
2
d
4
2
e
2
3
c
2
1
g
2
f
3
Manter tabela com
passos e custos
Figueiredo – 2010
Complexidade
Qual é a complexidade do algoritmo?
Complexidade idêntica a Dijkstra
1.Prim(G, o)
2.Para cada vértice v
3.
custo[v] = infinito
4.Define conjunto S = 0 // vazio
5.custo[o] = 0
6.Enquanto S != V
7.
Selecione u em V-S, tal que custo[u] é mínima
8.
Adicione u em S
9.
Para cada vizinho v de u faça
10.
Se custo[v] > w((u,v)) então
11.
custo[v] = w((u,v))
Usando filas de prioridade baseada em heap
n operações de remoção, m de atualização
O((m+n)log n) = O(m log n)
Figueiredo – 2010
Descobrindo a MST – Idéias II
Outra abordagem, diferente de BFS
mas também gulosa
Aresta de menor peso está na MST?
Aresta segundo menor peso está na MST?
Aresta de terceiro menor peso?
Cuidado com ciclos!
Figueiredo – 2010
Descobrindo a MST – Idéias II
Dado G=(V, E)
Construir MST, T=(V, E')
Inicialmente E' está vazio
Adicionar arestas de E em ordem crescente
Se aresta gerar um ciclo em T, então
descarte-a e continue
Algoritmo de Kruskal
Figueiredo – 2010
Algoritmo de Kruskal
Idéia: construir T adicionado arestas de
menor peso
1
b
c
Exemplo
3
5
4
2
a
5
b
1
c
1
b
2
d
1
e
f
1
b
c
c
...
a
e
1
f
2
d
e
1
f
Figueiredo – 2010
Analizando o Algoritmo
Algoritmos de Prim e Kruskal produzem
sempre uma MST?
Mas isto é óbvio?
Como provar que algoritmo sempre
produz resultado desejado – uma MST
Duas propriedades de uma MST
Propriedade do ciclo (cycle property)
Propriedade do corte (cut property)
Figueiredo – 2010
Propriedade do Ciclo
Para qualquer ciclo C do grafo, se o peso
de uma aresta e do ciclo for maior do
que de todas as outras arestas do ciclo,
então e não pertence a MST
Prova por contradição
Assuma que aresta e pertence a MST, T
Mostrar que existe outra árvore geradora
T' com custo menor que não utiliza e
Concluir que aresta e não pode pertencer
a MST
Figueiredo – 2010