Algoritmo de PRIM para MST
Disciplina Análise de Algoritmos
Bacharelado em CC
Algoritmo de PRIM
• Utiliza a seguinte estratégia para construir o corte a
cada etapa:
S = conjunto de vértices de Xk-1
• Utiliza uma estratégia análoga ao do Algoritmo de
Dijkstra para pegar a aresta de menor custo a cada
etapa, atravessando o corte.
Algoritmo de Dijkstra
Input: Grafo G (dirigido ou não), vértice S, cada aresta e tem uma dist(e)
associada.
Output: para cada vértice v, dist(v) de S a v, distância do menor caminho entre S
e v.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Para todo vértice u
dist(u) = infinito
prev(u) = nil
dist(S) = 0
Constrói H = fila com prioridade contendo os vértices de G (prioridade é a
menor distância a raiz S)
While H ≠
u = deletemin(H)
Para cada aresta uv
se dist(v) > dist(u) + dist(u,v)
dist(v) = dist(u) + dist(u,v)
recoloca(H,v)
(v é recolocado na fila segundo sua prioridade)
Algoritmo de PRIM
Input: Grafo G (dirigido ou não), vértice S, cada aresta e tem um custo(e)
associada.
Output: MST de G
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Para todo vértice u
custo(u) = infinito
prev(u) = nil
Escolhe vértice inicial u0
Custo(u0) = 0
Constrói H = fila com prioridade contendo os vértices de G (prioridade é o
custo do vértice)
While H ≠
u = deletemin(H)
Para cada aresta uv se custo(v) > custo(u,v)
custo(v) = custo(u,v)
recoloca(H,v)
(v é recolocado na fila segundo sua prioridade)
Análise de Complexidade de PRIM
• A mesma do algoritmo de Dijkstra
• Esquema geral:
|V|.insert + |V|.deletemin + |E|.recoloca
• Fila implementada como array:
|V|.O(1) + |V|.|V| + |E|.O(1) = O(|V|2) + O(|V|+|E|) =
O(|V|2)
• Fila implementada como heap binário:
|V|.log(|V|) + |V|.log(|V|) + |E|.log(|V|) =
(|E| + |V|).log(|V|)
Exemplo de Aplicação
A
6
4
5
B
2
C
1
2
5
D
E
3
4
4
F
Fila com prioridade H
S
Etapa 0
{}
A
B
C
D
E
F
0/nil /nil /nil /nil /nil /nil
Exemplo de Aplicação
A
6
4
5
C
1
2
B
2
D
5
E
3
4
4
F
Fila com prioridade H
S
Etapa 0
{}
Etapa 1
{A}
A
B
C
D
E
F
0/nil /nil /nil /nil /nil /nil
5/A
6/A
4/A
/nil /nil
Exemplo de Aplicação
A
6
4
5
C
1
2
B
2
D
5
E
3
4
4
F
Fila com prioridade H
S
A
Etapa 0
{}
0/nil
Etapa 1
Etapa 2
B
C
D
E
F
/nil /nil
/nil
/nil
/nil
{A}
5/A
6/A
4/A
/nil
/nil
{A,D}
2/D
2/D
/nil
4/D
Exemplo de Aplicação
A
6
4
5
C
1
2
B
2
D
5
E
3
4
4
F
Fila com prioridade H
S
A
Etapa 0
{}
0/nil
Etapa 1
B
C
D
E
F
/nil /nil
/nil
/nil
/nil
{A}
5/A
6/A
4/A
/nil
/nil
Etapa 2
{A,D}
2/D
2/D
/nil
4/D
Etapa 3
{A,D,B}
1/B
/nil
4/D
Exemplo de Aplicação
A
6
C
4
5
1
B
2
2
D
5
E
3
4
4
F
Fila com prioridade H
S
A
Etapa 0
{}
0/nil
Etapa 1
B
C
D
E
F
/nil /nil
/nil
/nil
/nil
{A}
5/A
6/A
4/A
/nil
/nil
Etapa 2
{A,D}
2/D
2/D
/nil
4/D
Etapa 3
{A,D,B}
1/B
/nil
4/D
Etapa 4
{A,D,B,C}
5/C
3/C
Exemplo de Aplicação
A
6
C
4
5
1
B
2
2
D
5
E
3
4
4
F
Fila com prioridade H
S
A
Etapa 0
{}
0/nil
Etapa 1
B
C
D
E
F
/nil /nil
/nil
/nil
/nil
{A}
5/A
6/A
4/A
/nil
/nil
Etapa 2
{A,D}
2/D
2/D
/nil
4/D
Etapa 3
{A,D,B}
1/B
/nil
4/D
Etapa 4
{A,D,B,C}
5/C
3/C
Etapa 5
{A,D,B,C,F}
4/F
Exemplo de Aplicação
A
6
C
4
5
1
B
2
2
D
5
E
3
4
4
F
Fila com prioridade H
S
A
Etapa 0
{}
0/nil
Etapa 1
B
C
D
E
F
/nil /nil
/nil
/nil
/nil
{A}
5/A
6/A
4/A
/nil
/nil
Etapa 2
{A,D}
2/D
2/D
/nil
4/D
Etapa 3
{A,D,B}
1/B
/nil
4/D
Etapa 4
{A,D,B,C}
5/C
3/C
Etapa 5
{A,D,B,C,F}
4/F