ACH2024 Aula09e10 ArvoreGeradoraMinima Prim e Kruskal

Prévia do material em texto

1
ACH2024 
Aulas 09 e 10 – Grafos:
Árvore Geradora Mínima
Algoritmos de Prim e de Kruskal
Profa. Ariane Machado Lima
2Slide do livro do Ziviani – cap 7
3
Slide do livro do Ziviani – cap 7
4
Slide do livro do Ziviani – cap 7
5
Slide do livro do Ziviani – cap 7
6
Slide do livro do Ziviani – cap 7
A
7
Slide do livro do Ziviani – cap 7
8
Exemplo
Como gerar a AGM a partir do grafo do slide 3?
Como seria a implementação desse algoritmo?
9
Algoritmo de Prim
Uma importante questão é: como selecionar essa aresta leve…para isso:
Q: fila de prioridade contendo os vértices de G que ainda estão fora da 
AGM. 
 Qual deveria ser o vértice de maior prioridade?
 Aquele que é a ponta de uma aresta leve naquele dado momento
 Então o que deveria ser a chave desses vértices?
 key[v]: peso da aresta de menor peso que conecta o vértice v (que 
ainda não está na AGM parcial) a um vértice que já se encontra nela. 
Quanto menor key[v] maior a prioridade nesta fila
π[v]: (antecessor) vértice da outra ponta desta aresta (que já está na AGM)
Quando um vértice u sai de Q (porque tem o menor key),(u, π[u]) é a aresta 
leve que acaba de entrar 
10
Algoritmo de Prim
Uma importante questão é: como selecionar essa aresta leve…para isso:
Q: fila de prioridade contendo os vértices de G que ainda estão fora da 
AGM. 
 Qual deveria ser o vértice de maior prioridade?
 Aquele que é a ponta de uma aresta leve naquele dado momento
 Então o que deveria ser a chave desses vértices?
 key[v]: peso da aresta de menor peso que conecta o vértice v (que 
ainda não está na AGM parcial) a um vértice que já se encontra nela. 
Quanto menor key[v] maior a prioridade nesta fila
π[v]: (antecessor) vértice da outra ponta desta aresta (que já está na AGM)
Quando um vértice u sai de Q (porque tem o menor key),(u, π[u]) é a aresta 
leve que acaba de entrar 
11
Algoritmo de Prim
Uma importante questão é: como selecionar essa aresta leve…para isso:
Q: fila de prioridade contendo os vértices de G que ainda estão fora da 
AGM. 
 Qual deveria ser o vértice de maior prioridade?
 Aquele que é a ponta de uma aresta leve naquele dado momento
 Então o que deveria ser a chave desses vértices?
 key[v]: peso da aresta de menor peso que conecta o vértice v (que 
ainda não está na AGM parcial) a um vértice que já se encontra nela. 
Quanto menor key[v] maior a prioridade nesta fila
π[v]: (antecessor) vértice da outra ponta desta aresta (que já está na AGM)
Quando um vértice u sai de Q (porque tem o menor key),(u, π[u]) é a aresta 
leve que acaba de entrar 
12
Algoritmo de Prim
Uma importante questão é: como selecionar essa aresta leve…para isso:
Q: fila de prioridade contendo os vértices de G que ainda estão fora da 
AGM. 
 Qual deveria ser o vértice de maior prioridade?
 Aquele que é a ponta de uma aresta leve naquele dado momento
 Então o que deveria ser a chave desses vértices?
 key[v]: peso da aresta de menor peso que conecta o vértice v (que 
ainda não está na AGM parcial) a um vértice que já se encontra nela. 
Quanto menor key[v] maior a prioridade nesta fila
π[v]: (antecessor) vértice da outra ponta desta aresta (que já está na AGM)
Quando um vértice u sai de Q (porque tem o menor key),(u, π[u]) é a aresta 
leve que acaba de entrar 
13
G: grafo
 w: pesos das arestas
 r: raiz
Isso significa que eu vou 
adicionar u à AGM parcial, 
com a aresta (u,Π[u]) .
Já que u agora faz parte 
da AGM parcial, todas as 
arestas que conectam u a 
um vértice em Q (ie, que 
estão fora da AGM parcial) 
são “candidatas” a arestas 
leves, por isso preciso 
atualizar o key dos 
vértices v adjacentes a u 
de forma a considerar a 
aresta (v, u) como possível 
aresta leve
14
Slide do livro do Ziviani – cap 7
key
rótulo do vértice
Π (antecessor)
corte
15
Outro exemplo
http://www.each.usp.br/lauretto/ACH2024_2015/Exemplo_Algoritmo_Prim.pdf
16
Complexidade
Depende da implementação de Q….
17
Complexidade
Depende da implementação de Q….
Se Q for uma lista linear simples 
não ordenada: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(V)
 Linha 6-7: O(V2)
Linhas 8-11: O(A) no total 
(assumindo lista de adjacência) 
Complexidade: O(V) + O(V2) +O(A) 
= O(V2)
18
Complexidade
Depende da implementação de Q….
Se Q for uma lista linear simples 
não ordenada: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(V)
 Linha 6-7: O(V2)
Linhas 8-11: O(A) no total 
(assumindo lista de adjacência) 
Complexidade: O(V) + O(V2) +O(A) 
= O(V2)
Arg! Precisa melhorar….
19
Construção do Heap
Extrai do heap elemento de maior 
prioridade e reajuste o heap
Aumenta prioridade de um elemento
Heap no algoritmo de Prim
Vetor de bits para saber em O(1) se v 
está em Q
20
Complexidade
Depende da implementação de Q….
Se Q for um heap binário: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(lg V)
Linha 6-7: O(V lg V)
Loop 8: O(A) no total 
Linha 11: O(lg V)
Linhas 8-11: O(A lg V) no total 
(assumindo lista de 
adjacência)
Complexidade: O(V) + O(V lg V) 
+O(A lg V) = O( A lg V)
Bem melhor….
21
Complexidade
Depende da implementação de Q….
Se Q for um heap binário: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(lg V)
Linha 6-7: O(V lg V)
Loop 8: O(A) no total 
Linha 11: O(lg V)
Linhas 8-11: O(A lg V) no total 
(assumindo lista de 
adjacência)
Complexidade: O(V) + O(V lg V) 
+O(A lg V) = O( A lg V)
Bem melhor…. Por que essa última igualdade?
Assumindo que G é conexo…
O que aconteceria com esse algoritmo se não fosse?
22
Complexidade
Depende da implementação de Q….
Se Q for um heap binário: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(lg V)
Linha 6-7: O(V lg V)
Loop 8: O(A) no total 
Linha 11: O(lg V)
Linhas 8-11: O(A lg V) no total 
(assumindo lista de 
adjacência)
Complexidade: O(V) + O(V lg V) 
+O(A lg V) = O( A lg V)
Bem melhor…. Por que essa última igualdade?
Assumindo que G é conexo…
O que aconteceria com esse algoritmo se não fosse?
23
Complexidade
Depende da implementação de Q….
Se Q for um heap binário: 
Linhas 1 a 5: O(V)
Loop da linha 6: V vezes
Linha 7: O(lg V)
Linha 6-7: O(V lg V)
Loop 8: O(A) no total 
Linha 11: O(lg V)
Linhas 8-11: O(A lg V) no total 
(assumindo lista de 
adjacência)
Complexidade: O(V) + O(V lg V) 
+O(A lg V) = O( A lg V)
Se usar heap Fibonacci, O(A + V lg V), que é ainda melhor caso quando |V| < |A|
24
Algoritmo de Prim
Uma árvore, inicialmente vazia, cresce até chegar 
a ser uma AGM
A cada passo um vértice é acrescentado a essa 
árvore
25
Algoritmo de Kruskal
Uma floresta A contém inicialmente todos os vértices 
isolados (cada vértice um componente conectado)
A cada passo, é adicionada uma aresta segura: 
a aresta de menor peso que conecta dois componentes 
conectados DISTINTOS
Por eficiência, cada componente conectado é 
representado por uma estrutura de dados que 
implementa conjuntos disjuntos.
26
Algoritmo de Kruskal
Uma floresta A contém inicialmente todos os vértices 
isolados (cada vértice um componente conectado)
A cada passo, é adicionada uma aresta segura: 
a aresta de menor peso que conecta dois componentes 
conectados DISTINTOS
Por eficiência, cada componente conectado é 
representado por uma estrutura de dados que 
implementa conjuntos disjuntos.
27
Algoritmo de Kruskal
Cria um conjunto disjunto contendo apenas v
Encontra o conjunto daquele vértice
Une os conjuntos de u e de v em um só
28
Algoritmo de Kruskal29
Algoritmo de Kruskal
30
Conjuntos disjuntos
A complexidade do algoritmo de Kruskal depende 
da eficiência da estrutura de dados para 
conjuntos disjuntos (cap 21 do livro do 
Cormen).
http://www.each.usp.br/lauretto/ACH2024_2015/disjoint_sets.pdf
Também conhecidos como “Union-Find”
31
32
raiz da
33
34
Uma possível implementação do 
Find-SET
35
Uma possível implementação do 
Find-SET
FIND-SET(x)
 se x != p[x]
 retorna FIND-SET(p[x])
 retorna x
36
Sempre que eu ligo duas raízes com o mesmo rank eu aumento o 
rank da raiz do novo conjunto 
Após sucessivos aumentos, a árvore pode ficar bem desbalenceada 
e com uma altura grande
37
Pode-se aproveitar as buscas para 
melhorar o balanceamento da árvore!
FIND-SET(x)
 se x != p[x]
 retorna FIND-SET(p[x])
 retorna x
VERSÃO NOVA!
VERSÃO ANTIGA...
38
Efeito de um FIND-SET(a)
39
Algoritmo de Kruskal - Complexidade
L. 4: O(A lg A)
L. 2 + loop L.5: |V| MAKE-SET's + O(A) FIND-SET's e UNION's = 
O( V+A α(V) ), sendo α(V) é uma função que cresce muito lentamente, 
menos que o log(V)
Como G é conectado → |A| >= |V| -1 → O(A α(V) )
Como α(V) = O(lg V) = O(lg A), complexidade total: O(A lg A)
Como |A| < |V|2 → lg |A| < lg (|V|2) → lg |A| < 2 lg |V| → lg |A| = O(lg V)
→ Complexidade total O(A lg V) (a mesma do alg. de Prim)
E = A: conjunto de arestas
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39