ARVORES GERADORAS MINIMAS E O ALGORITMO DE KRUSKAL

grafos AGM

1. Universidade Federal de Alfenas Universidade Federal de Alfenas
Algoritmos em Grafos Algoritmos em Grafos
Aula 09 Aula 09
––
ÁÁ
rvore Geradora M rvore Geradora M
íí
nima: Algoritmo de nima: Algoritmo de
Kruskal Kruskal
Prof. Humberto C Prof. Humberto C
éé
sar Brandão de Oliveira sar Brandão de Oliveira
[email protected] [email protected]
**
mg.edu.br mg.edu.br

2. Relembrando aula passada... Relembrando aula passada...
•
Exemplo:
),(AV G
=
),('XV G
=

3. Relembrando aula passada... Relembrando aula passada...
.
)},{(
),(
1||||
}{
) ), ,(( _
fim
X retorna
enquanto fim
vu X X
X para segura vu aresta uma encontrar
faça V X enquanto
X
wAVG GENERICA AGM
∪ ←
− ≤
←
1. Corte
2. Aresta segura
3. Aresta leve

4. ÁÁ
rvore Geradora M rvore Geradora M
íí
nimanima
•
Dois
algoritmos cl algoritmos cl
áá
ssicos para a AGM ssicos para a AGM
:
▫ Kruskal;
▫ Prim;
•
Primeiro algoritmo: ▫ Boruvka.

5. ÁÁ
rvore Geradora M rvore Geradora M
íí
nimanima
••
PrimPrim
::
▫Gera uma 
áá
rvore  rvore 
úú
nicanica
;
▫Ao longo do algoritmo, o conjunto X sempre éuma árvore.
••
Kruskal Kruskal
::
▫Gera uma 
floresta floresta
, antes de gerar a AGM;
▫Existe garantia de ser apenas uma árvore apenas depois 
da última iteração.

6. Kruskal Kruskal
•
Na aula de hoje vamos estudar o algoritmo de Kruska l: ▫ Criado por Joseph Bernard Kruskal, Jr.
▫ Nascido em 1928.
▫ Terminou seu PhD na Universidade
de Princeton em 1956

7. ÁÁ
rvore Geradora M rvore Geradora M
íí
nimanima
••
Arestas seguras: Arestas seguras: ▫▫
PrimPrim
::
GA aresta segura ésempre a aresta de peso mínimo que 
conecta a árvore a um vértice não presente no conju nto X. ▫▫
Kruskal Kruskal
::
GA aresta segura ésempre uma aresta de peso mínimo no 
grafo que conecta dois componentes distintos (duas árvor es 
distintas na floresta).

8. Kruskal Kruskal
••
Ponto Chave: Ponto Chave: ▫ Ele encontra uma
aresta segura aresta segura
para adicionar àfloresta
encontrando,
de todas as arestas que conectam duas de todas as arestas que conectam duas
áá
rvores quaisquer, uma aresta de peso m rvores quaisquer, uma aresta de peso m
íí
nimonimo
;
RSe você reparar,
o corte acontece neste ponto o corte acontece neste ponto
... Mas para isso, é
efetuada uma adaptação no grafo original
•
Kruskaléconsiderado um
algoritmo guloso algoritmo guloso
, porque em cada passo
ele adiciona àfloresta uma
aresta de peso m aresta de peso m
íí
nimonimo
(daquelas que
ainda podem ser adicionadas).
▫ Ou seja, faz uma avaliação dentre todas as possibi lidades que
possui;

9. .
),(
)},{(
)( )(
' ),(
'
)(
}{
) ), ,(( _
fim
X retorne
para fim
se fim
vuão aplicarUni
vu X X
então v conjuntoDe u conjuntoDe se
faça A vu aresta cada para
crescente peso por Ade arestas as ordenar A
para fim
v nto criarConju
faça Vv vértice cada para
X
wAVG Kruskal AGM
∪ ←
≠
∈
←
∈
←
Kruskal

10. .
),(
)},{(
)( )(
' ),(
'
)(
}{
) ), ,(( _
fim
X retorne
para fim
se fim
vuão aplicarUni
vu X X
então v conjuntoDe u conjuntoDe se
faça A vu aresta cada para
crescente peso por Ade arestas as ordenar A
para fim
v nto criarConju
faça Vv vértice cada para
X
wAVG Kruskal AGM
∪ ←
≠
∈
←
∈
←
Kruskal
A princípio, o 
conjunto que 
guarda as arestas 
da AGM é vazio.

11. .
),(
)},{(
)( )(
' ),(
'
)(
}{
) ), ,(( _
fim
X retorne
para fim
se fim
vuão aplicarUni
vu X X
então v conjuntoDe u conjuntoDe se
faça A vu aresta cada para
crescente peso por Ade arestas as ordenar A
para fim
v nto criarConju
faça Vv vértice cada para
X
wAVG Kruskal AGM
∪ ←
≠
∈
←
∈
←
Kruskal
|V| árvores são 
criadas.

12. .
),(
)},{(
)( )(
' ),(
'
)(
}{
) ), ,(( _
fim
X retorne
para fim
se fim
vuão aplicarUni
vu X X
então v conjuntoDe u conjuntoDe se
faça A vu aresta cada para
crescente peso por Ade arestas as ordenar A
para fim
v nto criarConju
faça Vv vértice cada para
X
wAVG Kruskal AGM
∪ ←
≠
∈
←
∈
←
Kruskal O conjunto de 
arestas é
ordenado em 
função dos 
pesos. Condição 
necessária para a 
criação da AGM 
através de 
Kruskal

13. .
),(
)},{(
)( )(
' ),(
'
)(
}{
) ), ,(( _
fim
X retorne
para fim
se fim
vuão aplicarUni
vu X X
então v conjuntoDe u conjuntoDe se
faça A vu aresta cada para
crescente peso por Ade arestas as ordenar A
para fim
v nto criarConju
faça Vv vértice cada para
X
wAVG Kruskal AGM
∪ ←
≠
∈
←
∈
←
Kruskal
Para cada aresta 
do vetor 
ordenado
Se ue vsão de 
árvores distintas, 
a aresta (u,v)é
adicionada ao 
conjunto Xe é
aplicada uma 
união das 
árvores de ue v.

14. AGM utilizando  AGM utilizando 
Kruskal Kruskal
•
Considerando o grafo a seguir... Vamos criar
passo passo
**
aa
**
passo passo
a AGM utilizando Kruskal...

15. AGM utilizando  AGM utilizando 
Kruskal Kruskal
••
11
ºº
passo: passo:
criar um(a) conjunto/árvore para cada vértice.
{
}
}{},{}, {}, {},{},{},{},{},{i h g f e d c b a

16. AGM utilizando  AGM utilizando 
Kruskal Kruskal
••
22
ºº
passo: passo:
ordenar as arestas do conjunto A.
{
}
}{},{}, {}, {},{},{},{},{},{i h g f e d c b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
),();,(); ,();,();,();,(fd hb feed cb ha
A’

17. ••
33
ºº
passo: passo:
para cada aresta ordenada, faça...
AGM utilizando  AGM utilizando 
Kruskal Kruskal
{
}
}{},{}, {}, {},{},{},{},{},{i h g f e d c b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
),();,(); ,();,();,();,(fd hb feed cb ha
A’
g e h pertencem a 
mesma árvore na 
floresta?

18. •
3ºpasso: para cada aresta ordenada, faça...
AGM utilizando  AGM utilizando 
Kruskal Kruskal
{
}
}{},,{}, {},{}, {},{},{},{i hg f e d c b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
),();,(); ,();,();,();,(fd hb feed cb ha
A’
g e h pertencem a 
mesma árvore na 
floresta?
Não... Então...
União das árvores 
de g e h e adição da 
aresta na AGM

19. •
3ºpasso: para cada aresta ordenada, faça...
AGM utilizando  AGM utilizando 
Kruskal Kruskal
{
}
}{},,{}, {},{}, {},{},{},{i hg f e d c b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
),();,(); ,();,();,();,(fd hb feed cb ha
A’
ce ipertencem a 
mesma árvore na 
floresta?

20. {
}
},{}, {},{},{},,{},{},{hg f e dic b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
•
3ºpasso: para cada aresta ordenada, faça...
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de ce ie adição da 
aresta na AGM

21. {
}
},{}, {},{},{},,{},{},{hg f e dic b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
•
3ºpasso: para cada aresta ordenada, faça...
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
fe gpertencem a 
mesma árvore na 
floresta?

22. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,{},{}, {},,{},{},{hgf e dic b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de fe ge adição da 
aresta na AGM

23. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,{},{}, {},,{},{},{hgf e dic b a
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
a e bpertencem a 
mesma árvore na 
floresta?

24. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,{},{},{},,{},,{hgf e dic ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de ae be adição da 
aresta na AGM

25. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,{},{},{},,{},,{hgf e dic ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
c e fpertencem a 
mesma árvore na 
floresta?

26. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,{},{}, {},,{ihgfc e d ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de ce fe adição da 
aresta na AGM

27. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,{},{}, {},,{ihgfc e d ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
g e ipertencem a 
mesma árvore na 
floresta?

28. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,{},{}, {},,{ihgfc e d ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
(g,i) fecha um 
ciclo. Isso é
identificado 
porque ge i
pertencem a 
mesma árvore na 
estrutura auxiliar 
‘floresta’.

29. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,{},{}, {},,{ihgfc e d ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
c e dpertencem a 
mesma árvore na 
floresta?

30. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,{},{},,{ihgfdc e ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de ce de adição da 
aresta na AGM

31. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,{},{},,{ihgfdc e ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
h e ipertencem a 
mesma árvore na 
floresta?

32. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,{},{},,{ihgfdc e ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Fecha ciclo...

33. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,{},{},,{ihgfdc e ba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
a e hpertencem a 
mesma árvore na 
floresta?

34. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,{},{ihgfdcba e
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de ae he adição da 
aresta na AGM

35. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,{},{ihgfdcba e
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
b e cpertencem a 
mesma árvore na 
floresta?

36. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,{},{ihgfdcba e
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Fecha ciclo...

37. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,{},{ihgfdcba e
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
d e epertencem a 
mesma árvore na 
floresta?

38. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Não... Então...
União das árvores 
de de ee adição da 
aresta na AGM

39. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
e e fpertencem a 
mesma árvore na 
floresta?

40. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Fecha ciclo...

41. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
b e hpertencem a 
mesma árvore na 
floresta?

42. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Fecha ciclo...

43. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
d e fpertencem a 
mesma árvore na 
floresta?

44. •
3ºpasso: para cada aresta ordenada, faça...
{
}
},,,,,,,,{ihgfedcba
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’
Fecha ciclo...

45. •
O conjunto X (arestas da AGM) foi composto ao longo da execução
do Kruskal, onde apenas as arestas não marcadas de A’foram
adicionadas àárvore.
);,();,();, (); ,();,(); ,();,();,(ih dcig fc ba gf ic hg
AGM utilizando  AGM utilizando 
Kruskal Kruskal
),();,(); ,();,();,();,(fd hb feed cb ha
A’

46. Anima Anima
çç
ão na Web do algoritmo de  ão na Web do algoritmo de 
Kruskal Kruskal •
Pode ser feito passo a passo. Bom para entendimento geral do
algoritmo:
▫ http://students.ceid.upatras.gr/~papagel/project/k ruskal.htm

47. •
Qual éa complexidade do algoritmo de Kruskal?
•
Ela de depende quais estruturas?
•
Proponha uma estrutura eficiente para armazenar e
efetuar as operações na floresta e nas árvores do
algoritmo de Kruskal.
Exerc Exerc
íí
ciocio

48. Bibliografia •
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; 
(2002). Algoritmos –Teoria e Prática. Tradução da 2 ª
edição americana. Rio de Janeiro. Editora Campus.
•
ZIVIANI, N. (2007). Projeto e Algoritmos com 
implementações em Java e C++. São Paulo. Editora 
Thomson;
48