Árvore Geradora de Peso
Mínimo
Davi Martins
Fábio Ávila
Introdução

Apresentação do problema
 Diferenciação


Idéia geral do algoritmo
Algoritmo de Prim
 Leve

do problema de distâncias
modificação do algoritmo de distâncias
Algoritmo de Kruskal
 Idéia
alternativa - menor aresta disponível, se esta não
fechar ciclo

Custos
Apresentação do problema

Partindo de um Grafo G=(V,E)
 Conexo
 Não-direcionado

Deseja-se encontrar árvore geradora de peso
mínimo (T)
 Minimum
Cost Spanning Tree (MCST)
 Subgrafo de G
 Contém todos os vértices de G (conceito de árvore
geradora)
 Possui (V-1) arestas
Exemplo 1
8
7
b
c
d
9
4
2
11
a
4
i
7
14
6
8
10
h


e
1
g
2
f
Peso total: 37
Árvore não-única. Removendo a aresta (b,c) e trocando-a
pela (a,h) leva a outra árvore geradora com peso 37.
Exemplo 2
16
1
21
19
2
5
11
6
6
33
3
14
10
5


18
4
Peso total: 56
Árvore geradora de peso mínimo única.
Idéia geral do algoritmo

Algoritmo genérico
1 A  Ø
2 Enquanto A não forma uma árvore geradora faça
3
Ache uma aresta (u,v) segura para A
4
A  A U {(u,v)}
5 Retorne (A)

Resta saber como achar arestas seguras
Partições




Um corte (S,V-S) de um grafo não direcionado G=(V,E) é uma
partição de V.
Uma aresta pode atravessar um corte
Um corte respeita um conjunto de arestas se o conjunto não possuir
nenhuma aresta que atravesse o corte
Uma aresta é leve se o seu peso é o mínimo de qualquer aresta
atravessando o corte.
8
b
7
c
d
9
4
2
a
i
11
7
e
14
4
6
8
10
h
S
1
g
2
f
V-S
Teorema

Seja G=(V,E) um grafo com pesos conexo e não
direcionado. Seja A um subconjunto de E contido
em alguma MCST para G. Seja (S,V-S) um corte
que respeita A, e seja (u,v) uma aresta leve
atravessando (S,V-S). Então, a aresta (u,v) é
segura para A.
Achando uma MCST com partições parciais
8
b
7
c
d
9
4
2
11
a
14
4
i
e
6
7
8
10
h
1
g
2
f
Diferenciação do problema de distâncias

No problema de distâncias, procurava-se sempre o
caminho mais curto saindo de um vértice inicial.


A única diferença entre os dois algoritmos é que o mínimo
não é mais tomado como o comprimento total do caminho,
mas sim como o custo de uma aresta.


Guarda-se sempre a distância mínima de cada vértice ao vértice
inicial
Trabalha-se sempre com os vértices dentro da partição, buscando
sempre um vértice fora da partição atual (formando uma aresta
considerada segura)
O resto do algoritmo é basicamente o mesmo
Algoritmo de Prim


Algoritmo muito similar ao SSSP
Árvore T definida inicialmente como uma árvore contendo
apenas o vértice inicial


Seguramente, um subgrafo da MCST
Em cada iteração, procura-se achar a aresta de custo
mínimo conectando T a vértices fora de T.
Algoritmo MCST-Prim (G)
Entrada: G (um grafo conexo com pesos não direcionado)
Saída: T (uma árvore geradora de peso mínimo de G)
Início
T  Ø;
Para todo vértice w faça
w.marca  Falso;
w.custo  ;
Atribua a (x,y) uma aresta de peso mínimo em G;
x.marca  Verdadeiro;
Para todas as arestas (x,z) faça
z.aresta  (x,z);
z.custo  custo(x,z);
Enquanto existir um vértice não marcado faça
w  vértice não marcado com menor w.custo;
w.marca  Verdadeiro;
Adicione w.aresta a T;
Para todos os vértices (w,z) faça
Se não z.marca então
Se custo(w,z) < z.custo então
z.aresta  (w,z);
z.custo  custo(w,z);
Fim
4
a
b
11
8
8
7
h
a
i
1
b
c
7
c
d
9
2
4
14
6
g
d
e
f
10
f
2
g
e
h
i
Algoritmo MCST-Prim (G)
Entrada: G (um grafo conexo com pesos não direcionado)
Saída: T (uma árvore geradora de peso mínimo de G)
Início
T  Ø;
Para todo vértice w faça
w.marca  Falso;
w.custo  ;
Atribua a (x,y) uma aresta de peso mínimo em G;
x.marca  Verdadeiro;
Para todas as arestas (x,z) faça
z.aresta  (x,z);
z.custo  custo(x,z);
Enquanto existir um vértice não marcado faça
w  vértice não marcado com menor w.custo;
w.marca  Verdadeiro;
Adicione w.aresta a T;
Para todos os vértices (w,z) faça
Se não z.marca então
Se custo(w,z) < z.custo então
z.aresta  (w,z);
z.custo  custo(w,z);
Fim
16
a
b
5
21
11
19
6
f
33
c
14
10
e
d
18
a
b
c
d
e
f
Custo do Algoritmo de Prim




Depende de como se implemente os procedimentos de busca
do menor elemento. Usaremos heaps.
O procedimento de extrair o menor elemento dos candidatos
possíveis ao redor de um vértice leva no máximo (log |V|)
operações, onde |V| é o número de vértices do grafo. Essa
comparação acontece |V| vezes. Portanto, essa parte do
algoritmo tem tempo de execução O(|V| log |V|)
O último laço para é executado O(|E|) vezes no total.
Sabemos que operações de atualização em heaps é O(log |V|),
portanto esta última parte leva a O(|E| log |V|)
Somando-se os tempos dos trechos, temos:
O(|V| log |V|) + O(|E| log |V|) = O((|E| + |V|) log |V|)
Algoritmo de Kruskal

Árvore T definida inicialmente como uma floresta
contendo todos os vértices do grafo original G


Seguramente, um subgrafo da MCST
Primeiro ordena os pesos de cada aresta, partindo do
menor peso para o maior

Checa se os vértices que formam arestas candidatas não estão na
mesma árvore (ou seja, se fecha um ciclo)
Algoritmo MCST-Kruskal (G)
Entrada: G (um grafo conexo com pesos não direcionado)
Saída: T (uma árvore geradora de peso mínimo de G)
Início
T  Ø;
Para todo vértice w faça
Adicione w a T;
Ordene os pesos das arestas de T;
Para todas as arestas (x,z), na ordem crescente, faça
Se u e v não pertencem à mesma árvore então
Adicione (u,v) a T;
Fim
16
1
2
5
21
19
11
6
6
33
3
14
10
5
18
4
Algoritmo MCST-Kruskal (G)
Entrada: G (um grafo conexo com pesos não direcionado)
Saída: T (uma árvore geradora de peso mínimo de G)
Início
T  Ø;
Para todo vértice w faça
Adicione w a T;
Ordene os pesos das arestas de T;
Para todas as arestas (x,z), na ordem crescente, faça
Se u e v não pertencem à mesma árvore então
Adicione (u,v) a T;
Fim
8
4
7
b
c
d
9
2
11
a
7
4
i
e
14
6
8
10
h
1
g
2
f
Custo do Algoritmo de Kruskal



O procedimento para ordenar as arestas é O(|E| log |E|),
obedecendo os critérios de algoritmos de ordenação por
comparação.
Os tempos da parte de detecção dos vértices fazendo parte da
mesma árvore e junção dos vértices são O(|E| log |E|),
determinado usando as heurísticas de união por classificação
e compressão de caminho.
Portanto, o tempo do algoritmo de Kruskal é
O(|E| log |E|)
Conclusão


Tradução da parte de MCST do Manber disponível
para consulta.
Consultar livro “Introduction to Algorithms”,
Thomas H. Cormen, Charles E. Leiserson e Ronald L. Rivest
 Apresentação
mais amigável do assunto