Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim e de Kruskal - Coggle Diagram
Algoritmo de Prim e de Kruskal
Algoritmo de Prim
Aplicações
Todos os tipos de redes(comunicação, transporte, elétrica, etc )
Para classificação em arqueologia, biologia, sociologia e outras ciências
Constrói uma arvores geradora mínima
Algoritmo
Começa por um vértice arbitrário do grafo
A cada interação ele expande anexando o vértice mais próximo(com a aresta com menor peso) que não está na árvore
O algoritmo para após todos os vértices do grafo terem sido adicionados na árvore
é necessário anexar 2 rótulos, o nome do vértice mais próximo e o peso
vértices que não estão na arvores são divididos em dois
Fringe
são os vértices adjacentes a pelo menos um vértices da arvores mas não estão na arvore
Unseen
São os outros vértices da arvore
Eficiência
Matriz com os pesos e fila de prioridade em array desordenado
Θ(|V|²)
Lista de adjacência e fila de prioridade em heap mínima
O(|E|log|V|)
Algoritmo de Kruskal
Eficiência
O(|E|log|E|)
Algoritmo
ordena de forma não crescente as arestas pelos seus pesos
começando com o subgrafo vazio, examina esta lista classificada e adiciona a próxima aresta ao subgrafo atual
Caso não forme um ciclo, pulasse essa aresta
Podemos considerar as operações do algoritmo como uma progressão através de florestas contendo todos os vértices de um determinado grafo e algumas de arestas do mesmo
Union-Find
é uma ADT
Operações
Makeet
Cria um conjunto de um elemento x
Find
Constrói a união de dois subconjuntos disjuntos
Union
retorna um subconjunto com x
Alternativas para a implementação
Quick Find
otimiza a eficiência temporal do Find
Temos com as operações com essas eficiências
Makeet
Θ(n)
Union
sem unir pelo tamanho - Θ(n²)
pior caso usando unir pelo tamanho - O(n log n
Find
Θ(1)
Quick Union
otimiza a eficiência temporal do Union
Temos com as operações com essas eficiências
Makeet
Θ(n)
Union
Θ(1)
Find
O(n)
com unir pelo tamanho ou união por posto
1 more item...