Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André, n = número de elementos em S…
IF672 (2020.1) - Levitin Aluno: Marcos André
(9) Greedy Technique (318-322)
(9.1) Algoritmo de Prim
Conectar pontos da forma mais barata possível
Caminho entre cada par de pontos
Aplicações
Design de redes
Conectividade
Identificação de clusters
Classificações
Soluções aproximadas
Uso de um grafo
"Spanning" Tree
Spanning Tree mínima para um grafo de pesos conectado
Melhor forma de encontrar uma é com Prim
Funcionamento
Sequência de subárvores expandidas
Cada subárvore é expandida por um vértice
Informar peso da aresta
Aplicação semelhante a Dijkstra
Sempre gera uma Spanning Tree mínima
Eficiência
Matriz de pesos e array não-ordenado
θ(|V|²)
Heap mínima e lista de adjacência
O(|E| log |V|)
(9.2) Algoritmo de Kruskal
Outra solução para o problema de spanning tree mínima
Funcionamento
Subgrafo acíclico com |V| -1 arestas no qual a soma dos pesos das arestas é a menor
Gera subgrafos não necessariamente conectados
Ordena as arestas em ordem não-decrescente dos seus pesos
Escaneia a lista ordenada
Adiciona a próxima aresta na lista ao subgrafo atual
Se cria ciclo, pula a aresta
Versão modificada é mais eficiente
União de árvores se elas não são iguais
Algoritmos Union-Find
Eficiência de O(|E| log |E|)
Disjoint Subsets e Algoritmos Union-Find
Particionamento de um elemento em "disjoint subsets"
Coleção de aplicações de Union-Find
Operações
makeset
find
union
Representante do subset
Algumas aplicações
Menor elemento
Alternativas de implementação
quick find
Array indexada pelos representantes (menor subset)
Subsets são listas ligadas
Operação union não muito eficiente
union by size
Eficiência geral
O(n log n + m)
quick union
Subsets são árvores enraizadas
A raiz é o representante
find não muito eficiente
union by size
union by rank
Eficiência geral
O(n+m log n)
Path compression
Eficiência um pouco pior que linear
n = número de elementos em S
m = número de "finds"