Algoritmos em Grafos
Celso C. Ribeiro
Caroline T. Rocha
PARTE 5: Árvore Geradora de Peso Mínimo
Algoritmos em Grafos
2
Árvore Geradora de Peso Mínimo
Dados:
G = (V,E) grafo não-orientado, com |V|=n e |E|=m
peso c(e), e  E
Problema
Obter F  E tal que:
o grafo G’=(V,F) é acíclico e conexo (G’ é gerador de G)
c(F) = eEc(e) é mínimo
Algoritmos em Grafos
3
Árvore Geradora de Peso Mínimo
Exemplo:
4
A
B
9
5
4
E
3
8
F
2
2
7
D
C
9
4
4
5
4
4
8
3
3
2
2
árvore geradora
peso = 24
árvore geradora
peso = 15
Algoritmos em Grafos
4
Árvore Geradora de Peso Mínimo
Algoritmo de Kruskal
Princípio: a aresta de menor peso sempre pertence à árvore
geradora de peso mínimo.
Prova:
Suponha que a aresta de peso mínimo não pertença à solução
ótima.
Inserindo-se a aresta de peso mínimo nesta solução ótima,
obtém-se um ciclo.
Pode-se obter uma nova árvore geradora removendo-se a
aresta de maior peso.
Esta nova árvore geradora teria peso menor do que a anterior,
portanto aquela solução não poderia ser ótima.
Algoritmos em Grafos
5
Árvore Geradora de Peso Mínimo
Algoritmo de Kruskal
Criar uma lista L com as arestas ordenadas em
ordem crescente de pesos.
Criar |V| subárvores contendo cada uma um nó
isolado.
F  
contador  0
Enquanto contador < |V|-1 e L   faça
Seja (u,v) o próximo arco de L.
L  L – {(u,v)}
Se u e v não estão na mesma subárvore então
F  F  {(u,v)}
Unir as subárvores que contêm u e v.
contador  contador + 1
fim-se
fim-enquanto
Algoritmos em Grafos
6
Árvore Geradora de Peso Mínimo
Exemplo:
4
A
Lista L
B
9
5
4
3
E
2
7
D
8
F
2
3
C
9
c(F) = 15
11
2
4
7
Subárvores
{A
{{ A
A,
} }{D{A,{B
}{{B
B,
A,
}B}DB,
}{ }C
{{C,
C,
B
{} C,
D,
}F{{}E,
E,
D
C,}F{FE,
D
}}{{F}C,
E}{}E,
{DEF}{}F
} }
e
c(e)
(C,F)
2
(E,F)
2
(A,D)
3
(C,E)
X
3
(A,B)
4
(A,E)
4
(B,F)
5
(D,F)
7
(B,C)
8
(B,E)
9
(C,D)
9
Algoritmos em Grafos
7
Árvore Geradora de Peso Mínimo
Exemplo:
4
B
C
4
Lista L
6
7
A
3
D
8
M
L
5
4
J
6
H
7
1
E
4
I
3
2
G
2
3
2
F
c(F)
c(F)==24
10
13
16
20
1
3
5
7
Subárvores
{ A{{}AA
{{}{A
A,
}{A,
}B{B{B,
}B
B
{} }B
C,
}{ }{CD,
{C,
}C,
C
{E,
D,
C,
}{D,
{F,
D,
D
E,
D,
D,
E,
G,
{}E
L,
E,
D,
E,
L,
J,
}{F,
LE,
LE
F,
L{G,
}}}LF
G,J
}{} {JF
} F}} }
e
c(e)
(D,E)
1
(D,L)
2
(F,J)
2
(G,J)
2
(C,D)
3
(E,F)
3
(H,I)
3
(A,B)
4
(B,C)
4
…
…
{{GF,
{ }F,
J }G,
{ HJ
{ }G
H
{} H,
}{{I {H
}{ HI} }}{ M
J{ {{I}}M
}I }}{ {L
M{M
}}M} {} M }
Algoritmos em Grafos
8
Árvore Geradora de Peso Mínimo
Exemplo:
4
B
C
4
Lista L
6
7
A
3
D
8
M
L
5
4
J
6
H
7
1
E
4
I
3
2
G
2
3
2
F
c(F) = 33
24
28
Subárvores
{ {A,A,B,B,C,C,D,D,E,E,F,F,G,
G,H,J,I,LJ,} L }
{ A, B, C, D, E, F, G, H, I, J, L, M }
{ H, I }{ M {} M }
e
c(e)
...
...
(A,I)
4
(J,L)
X
4
(G,M)
5
(C,M)
6
(I,J)
6
(A,M)
7
(G,H)
7
(B,L)
8
Algoritmos em Grafos
9
Árvore Geradora de Peso Mínimo
Algoritmo de Prim
Começar com uma árvore formada apenas por um nó
qualquer do grafo, ou pela aresta de peso mínimo.
A cada iteração, adicionar a aresta de menor peso que
conecta um nó já conectado a um nó não-conectado.
Algoritmos em Grafos
10
Árvore Geradora de Peso Mínimo
Algoritmo de Prim
Seja (u,v) a aresta de menor peso.
F  {(u,v)}
Para i = 1,...,n faça
Se c(i,u) < c(i,v) então prox(i)  u
Senão prox(i)  v
fim-para
prox(u), prox(v)  0, contador  0
Enquanto contador < n-2 faça
Seja j tal que prox(j)0 e c(j,prox(j)) é mínimo.
F  F  {(j,prox(j))}
prox(j)  0
Para i = 1,...,n faça
Se prox(i)  0 e c(i,prox(i)) > c(i,j) então
prox(i)  j
fim-para
contador  contador + 1
fim-enquanto
Algoritmos em Grafos
11
Árvore Geradora de Peso Mínimo
Exemplo:
4
A
B
9
5
4
3
E
2
2
7
D
8
F
3
9
C
c(F) = 15
11
2
4
7
Algoritmos em Grafos
12
Árvore Geradora de Peso Mínimo
Exemplo:
4
B
C
4
6
7
A
3
D
8
M
5
4
J
6
H
7
1
E
4
I
3
2
L
G
2
3
2
F
c(F)
c(F)==33
13
17
21
25
28
11
1
3
6
9
Algoritmos em Grafos
13