Algoritmos para Obtenção de Árvore
Geradora Mínima
Fabio Tirelo
Aplicação
 Obtenção de uma rede de comunicação
entre pontos de interesse com o menor custo
possível.
Algoritmo de Prim
 Algoritmo de busca em prioridade em grafos.
 Análogo ao algoritmo de obtenção de Árvore
Geradora de Caminho Mínimo, alterando somente o
cálculo da prioridade:
 O vértice escolhido a cada passo é o “mais próximo” a
qualquer vértice da árvore naquele momento e não somente
o mais próximo da origem.
Algoritmo de Prim...
A
6
A
5
1
B
5
3
D
C
2
4
6
B
5
C
6
E
D
F
E
F
Algoritmo de Prim...
A
6
A
5
6
1
B
5
3
D
C
2
4
6
1
B
5
C
6
E
D
5
F
E
F
Algoritmo de Prim...
A
6
A
5
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
C
6
E
D
4
F
Algoritmo de Prim...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
C
6
E
D
2
4
F
Algoritmo de Prim...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
C
6
E
D
2
4
F
Algoritmo de Prim...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
3
D
C
2
4
E
F
Algoritmo de Prim...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
3
D
C
2
4
E
F
Custo do Algoritmo de Prim
 O algoritmo de Prim tem um custo de tempo
O(n2), onde n é o número de vértices do
grafo.
Exercício:
 Encontre a AGM para o grafo abaixo,
utilizando o algoritmo de Prim:
A
5
7
2
E
F
1
4
P
3
3
O
3
6
7
B
6
9
8
G
5
N
9
4
8
9
C
D
5
7
J
7
H
I
5
M
13
2
11
K
7
6
L
10
Algoritmo de Kruskal
 Inicialmente, a AG é um grafo sem arestas
 Enquanto não houver incluído n-1 arestas, o
algoritmo obtém a aresta de menor custo,
incluindo-a na árvore caso esta não forme
ciclo.
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
D
C
2
4
6
B
5
C
6
E
D
1
F
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
D
C
2
2
4
6
B
5
C
6
E
D
1
F
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
D
C
2
4
6
B
5
C
6
E
D
1
F
3
2
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
D
C
2
4
6
B
5
C
6
E
D
1
F
3
2
4
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
5
1
B
5
3
D
C
2
4
6
B
5
C
6
E
D
1
F
3
2
4
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
3
D
C
2
4
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Algoritmo de Kruskal...
A
6
A
5
1
B
5
3
5
2
4
6
B
5
C
6
E
D
1
F
3
D
C
2
4
E
Arestas: AC DF BE CF AD BC AB CE EF
F
Exercício:
 Encontre a AGM para o grafo abaixo,
utilizando o algoritmo de Kruskal:
A
5
7
2
E
F
1
4
P
3
3
O
3
6
7
B
6
9
8
G
5
N
9
4
8
9
C
D
5
7
J
7
H
I
5
M
13
2
11
K
7
6
L
10
Custo do Algoritmo de Kruskal
 O algoritmo de Kruskal tem um custo de
tempo O(e log(e)), onde e é o número de
arestas do grafo.