Árvore de Espalhamento Mı́nima
1 / 56
Árvore de Espalhamento Mı́nima
Eduardo Camponogara
Departamento de Automação e Sistemas
Universidade Federal de Santa Catarina
DAS-9003: Introdução a Algoritmos
Árvore de Espalhamento Mı́nima
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
2 / 56
Árvore de Espalhamento Mı́nima
Introdução
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
3 / 56
Árvore de Espalhamento Mı́nima
Introdução
Introdução
◮
No projeto de circuitos integrados, frequentemente é
necessário conectar ”n” pontos de forma que eles sejam
eletricamente equivalentes.
◮
Isto pode ser feito utilizando n − 1 fios conectando dois pinos.
◮
Dentre todas as possı́veis formas de conexão, aquela que
utiliza menos fio é a mais desejável.
4 / 56
Árvore de Espalhamento Mı́nima
Introdução
Introdução
Modelo
◮
G = (V , E ) é um grafo onde V corresponde aos pinos, E é o
conjunto de possı́veis interconexões entre pares de pontos.
◮
Para cada aresta (u, v ) ∈ E temos o peso w (u, v )
especificando o custo da conexão.
5 / 56
Árvore de Espalhamento Mı́nima
6 / 56
Introdução
Introdução
Problema
◮
Encontre T ⊆ E que conecteP
todos os vértices, onde G [T ] é
acı́clico, e tal que w (T ) =
w (u, v ) seja minimizado.
(u,v )∈T
◮
Uma vez que G [T ] é um subgrafo acı́clico e conecta todos os
vértices, G [T ] deve ser uma árvore de espalhamento.
Árvore de Espalhamento Mı́nima
7 / 56
Introdução
Exemplo
8
4
7
c
b
d
9
2
11
a
14
e
6
7
8
4
4
i
10
g
h
1
2
f
Árvore de Espalhamento Mı́nima
8 / 56
Introdução
Exemplo
8
4
7
c
b
d
9
2
11
a
14
e
6
7
8
4
4
i
10
g
h
1
2
f
Árvore de Espalhamento Mı́nima
Introdução
Introdução
◮
Neste capı́tulo vamos examinar dois algoritmos para resolver o
problema da árvore de espalhamento mı́nima:
◮
◮
O algoritmo de Kruskal executa em tempo O(|E | lg |E |)
usando algoritmo de ordenação merge-sort e a estrutura de
dados union-find.
O algoritmo de Prim executa em tempo O(|E | + |V | lg |V |) se
utilizarmos um heap Fibonacci.
9 / 56
Árvore de Espalhamento Mı́nima
Introdução
Introdução
◮
Ambos os algoritmos são do tipo guloso.
◮
A cada passo, uma de muitas possı́veis opções deve ser
escolhida.
◮
A estratégia faz a escolha que dá o maior ganho imediato. Tal
estratégia não garante, em geral, encontrar a solução ótima.
◮
◮
Para o problema em consideração, a estratégia gulosa produz a
solução ótima.
Matróide.
10 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
11 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Crescendo uma árvore de espalhamento mı́nima
◮
Os algoritmos gulosos (Kruskal e Prim) seguem uma estrutura
genérica, a qual cresce a árvore de espalhamento mı́nima uma
aresta de cada vez.
◮
O algoritmo genérico manipula um subconjunto A que é
sempre um subconjunto da MST. A cada passo, uma aresta
(u, v ) é determinada e adicionada a A sem violar o invariante,
isto é, A ∪ {(u, v )} é também um subconjunto da MST.
◮
Uma aresta e é dita segura (“safe”) se e pode ser introduzida
em A sem afetar o invariante.
12 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Algoritmo Genérico
Generic-MST(G , w )
1)
A←Ø
2) while A does not form a spanning tree
3)
do find an edge (u, v ) that is safe for A
4)
A ← A ∪ {(u, v )}
5) return A
13 / 56
Árvore de Espalhamento Mı́nima
14 / 56
Crescendo uma árvore de espalhamento mı́nima
Definição
◮
Um corte (S, V − S) de um grafo não direcionado G = (V , E )
é uma partição de V .
S
V−S
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Exemplo
Grafo anterior
S = {a, b, d, e}
V − S = {c, i, h, g , f }
Definição
Uma aresta (u, v ) ∈ E atravessa o corte (S, V − S) se u ∈ S e
v∈
/ S.
15 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Teorema 24.1
◮
Seja G = (V , E ) um grafo conexo, não-direcionado onde
w : E → ℜ é uma função peso para as arestas.
◮
Seja A ⊆ E um subconjunto que está incluı́do em uma MST.
◮
Seja (S, V − S) qualquer corte de G tal que ∀e ∈ A temos
que e ∈
/ E (S, V − S). Então (S, V − S) respeita A.
◮
Seja (u, v ) uma aresta leve de E (S, V − S). Então (u, v ) é
uma aresta segura para A.
16 / 56
Árvore de Espalhamento Mı́nima
17 / 56
Crescendo uma árvore de espalhamento mı́nima
Prova
◮
◮
Suponha que T é uma MST que contém A, e assuma que T
não contém uma aresta leve (u, v ), uma vez que se T contém,
nada resta a provar.
A aresta (u, v ) forma um ciclo com o caminho p(u, v ) em T .
S
x
u
y
v
V−S
Árvore de Espalhamento Mı́nima
18 / 56
Crescendo uma árvore de espalhamento mı́nima
Prova
◮
Existe pelo menos uma aresta (x, y ) ∈ T tal que
(x, y ) ∈ E (S, V − S). Uma vez que (S, V − S) respeita A,
(x, y ) ∈
/ A.
◮
Uma vez (x, y ) faz parte do caminho único em T que conecta
u a v , removendo (x, y ) de T quebra T em dois componentes.
◮
Seja T ′ = T − {(x, y )} ∪ {(u, v )}
◮
Uma vez que (u, v ) é uma aresta leve, w (u, v ) ≤ w (x, y ),
portanto:
w (T ′ ) = w (T ) − w (x, y ) + w (u, v )
≤ w (T )
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Prova
◮
Mas T é uma árvore de espalhamento mı́nima, portanto
w (T ) ≤ w (T ′ ) ⇒ T ′ é uma árvore de espalhamento mı́nima.
◮
Ainda resta mostrar que a aresta (u, v ) é segura para A.
◮
Temos que A ⊆ T ′ , uma vez que A ⊆ T e (x, y ) ∈
/ A.
◮
Portanto A ∪ {(u, v )} ⊆ T ′ . Consequentemente, uma vez que
T ′ é uma árvore de espalhamento mı́nima, (u, v ) é segura
para A.
19 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Observações
◮
O teorema 24.1 nos dá um entendimento de como o algoritmo
GENERIC-MST trabalha. À medida que o algoritmo progride,
o conjunto A é sempre acı́clico.
◮
Em qualquer estágio do algoritmo, o grafo GA = (V , A) é uma
floresta e cada componente conexo de GA é uma árvore.
◮
◮
No começo cada árvore contém apenas 1 vértice
Qualquer aresta segura (u, v ) para A conecta apenas
componentes distintos de GA , uma vez que A ∪ {(u, v )} deve
ser acı́clico.
20 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Corolário 24.2
◮
Seja G = (V , E ) um grafo conexo, não-direcionado com uma
função peso w definida sobre E .
◮
Seja A um subconjunto de E que esteja incluı́do em alguma
MST, e seja C um componente conexo da floresta
GA = (V , A).
◮
Se (u, v ) é uma aresta leve conectando C a outro componente
de GA , então (u, v ) é uma aresta segura para A.
21 / 56
Árvore de Espalhamento Mı́nima
Crescendo uma árvore de espalhamento mı́nima
Prova
◮
O corte (C , V − C ) respeita A, e (u, v ) é portanto uma aresta
leve para o corte. 22 / 56
Árvore de Espalhamento Mı́nima
Algoritmos
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
23 / 56
Árvore de Espalhamento Mı́nima
Algoritmos
Algoritmos de Kruskal e de Prim
Os dois algoritmos a serem apresentados nesta seção se enquadram
dentro do algoritmo genérico. Cada um deles especı́fica uma regra
para escolher uma aresta segura.
24 / 56
Árvore de Espalhamento Mı́nima
Algoritmos
Algoritmos de Kruskal e de Prim
Algoritmo de Kruskal
◮
O conjunto A é uma floresta
◮
A aresta segura adicionada a A é sempre a aresta mais leve do
grafo que une dois componentes conexos de GA distintos.
25 / 56
Árvore de Espalhamento Mı́nima
Algoritmos
Algoritmos de Kruskal e de Prim
Algoritmo de Prim
◮
O conjunto A forma uma árvore única
◮
A aresta segura adicionada a A é sempre a aresta mais leve
que conecta a árvore a um vértice que não se encontra na
árvore.
26 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Kruskal
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
27 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Kruskal
O algoritmo de Kruskal
◮
O algoritmo seleciona dentre todas as arestas que conectam
dois componentes da floresta GA , a aresta (u, v ) de menor
peso.
◮
Sejam C1 e C2 os dois componentes a serem conectados por
(u, v ). Uma vez que (u, v ) deve ser uma aresta leve
conectando C1 a alguma outra árvore, o Corolário 24.2
garante que (u, v ) é uma aresta segura para C1 .
◮
O algoritmo de Kruskal pertence à classe dos algoritmos
gulosos.
◮
A cada passo, o algoritmo de Kruskal adiciona à floresta GA a
aresta de menor peso possı́vel.
28 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Kruskal
Algoritmo de Kruskal
MST-KRUSKAL (G , w )
1) A ← Ø
2) for each vertex v ∈ V [G ]
do MAKE-SET(v )
3) sort the edges of E by nondecreasing weight w
4) for each edge (u, v ) ∈ E , in order by nondecreasing weight
4.1) do FIND-SET(u) 6=FIND-SET(v )
4.2)
A ← A ∪ {(u, v )}
4.3)
UNION (u, v )
5) return A
29 / 56
Árvore de Espalhamento Mı́nima
30 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
31 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
32 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
33 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
34 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
35 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
36 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
37 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
38 / 56
Algoritmo de Kruskal
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
g
h
1
2
f
L = h(h, g )1 , (i, c)2 , (g , f )2 , (a, b)4 , (c, f )4 ,
(c, g )4 , (i, g )6 , (c, d)7 , (i, h)7 , (a, h)8 , (b, c)8 ,
(d, e)9 , (e, f )10 , (b, h)11 , (d, f )14 i
Árvore de Espalhamento Mı́nima
Algoritmo de Kruskal
Análise
◮
O tempo de execução do algoritmo de Kruskal sobre um grafo
G = (V , E ) depende da implementação da estrutura de dados
conjuntos-disjuntos.
◮
Inicialização consome O(|V |).
◮
Ordenação consome O(|E | lg |E |)
◮
Se utilizarmos a estrutura de dados UNION-FIND com a
heurı́stica compressão-de-caminho, cada operação sobre o
conjunto-disjunto é da ordem α(|E |, |V |) ∈ O(lg |E |)
◮
Há |E | operações sobre o conjunto-disjunto
◮
Portanto, o tempo computacional do algoritmo de Kruskal é
O(|E | lg |E |).
39 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Sumário
Introdução
Crescendo uma árvore de espalhamento mı́nima
Algoritmos
Algoritmo de Kruskal
Algoritmo de Prim
40 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Algoritmo de Prim
◮
Da mesma forma que o algoritmo de Kruskal, o algoritmo de
Prim é um caso especial do algoritmo genérico.
◮
O algoritmo de Prim tem a propriedade de que as arestas de A
sempre formam uma árvore única.
41 / 56
Árvore de Espalhamento Mı́nima
42 / 56
Algoritmo de Prim
Algoritmo de Prim
◮
O algoritmo inicia com um vértice arbitrário s e cresce a
árvore até que ela se torne uma MST.
◮
e ∗ é uma aresta mais leve conectando um vértice de GA com
um vértice de V − V (GA ).
V(Ga)
V−V(Ga)
Árvore de Espalhamento Mı́nima
43 / 56
Algoritmo de Prim
Implementação do algoritmo de Prim
◮
Durante a execução, os vértices que não estão em GA residem
em uma fila de prioridade Q.
◮
◮
◮
◮
Para cada vértice v , Key[v ] é o peso da aresta mais leve
conectando v a algum vértice de V [GA ].
Key[v ] = ∞ se tal aresta não existe.
O parâmetro π[v ] corresponde ao pai de v na MST.
Quando o algoritmo termina, a fila de prioridades Q está
vazia, e a MST A para G é dada por:
A = {(v , π[v ]) : v ∈ V − {s}}
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Algoritmo de Prim
MST-Prim(G , w , s)
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
Q ← V [G ]
for each u ∈ Q
Key[u]← ∞
Key[s]← 0
π[s] ←NIL
while Q 6= Ø
u ←extract min(Q)
for each v ∈ Adj[u]
if v ∈ Q and w (u, v ) <Key[v ]
π[v ] ← u
Key[v ] ← w (u, v )
end-if
end-for
end-while
44 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Análise
◮
O desempenho do algoritmo de Prim depende de como
implementamos a fila de prioridades Q.
◮
Se utilizamos o heap binário, então:
◮
◮
Os passos de inicialização de 1 a 5 são executados em tempo
O(|V |).
O laço while é executado |V | vezes
◮
◮
uma vez que EXTRACT MIN custa O(lg |V |) as chamadas
EXTRACT MIN vão custar O(|V | lg |V |)
O laço for, 8-11, é executado |E | vezes, uma vez que o
comprimento das listas de adjacência é no total 2|E |
◮
O custo total de redução de chaves é O(|E | lg |V |)
45 / 56
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Análise
◮
Portanto, o algoritmo de Prim tem tempo de execução
O(|V | lg |V | + |E | lg |V |) ∈ O(|E | lg |V |).
◮
Usando heaps Fibonacci, o algoritmo de Prim pode ter
complexidade reduzida para O(|V | lg |V | + |E |)
46 / 56
Árvore de Espalhamento Mı́nima
47 / 56
Algoritmo de Prim
Exemplo
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
48 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
49 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
50 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
51 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
52 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
53 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
54 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
55 / 56
Algoritmo de Prim
8
4
7
c
b
d
9
2
a
11
e
14
6
7
8
4
4
i
10
h
g
1
2
f
Árvore de Espalhamento Mı́nima
Algoritmo de Prim
Conclusões
◮
Fim!
◮
Obrigado pela presença
56 / 56