Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Prim e Kruskal - Coggle Diagram
Algoritmos de Prim e Kruskal
Prim
Conectar os pontos da forma mais 'barata'
Acha aglomerados que podem ser úteis para as mais diversas áreas
Solução: achar a menor árvore de abrangência
Ou seja, uma árvore de abrangência com o menor peso (soma dos pesos das arestas)
Deverá haver um caminho entre cada par
O número de árvores de abrangência cresce exponencialmente em um grafo denso
Para a achar a menor, é necessário usar um algoritmo eficiente, como o de Prim.
Algoritmo de Prim constrói a menor árvore de abrangência por meio de subárvores.
A partir de um vértice arbitrário, conecta-se ao próximo vértice não visitado com menor peso
Um vértice incluso por vez. São n - 1 interações.
Adicionar aos vértices informações: Vértice mais próximo e a distância.
Vértices não conectados ao vértices da árvore: distância infinita
Ou separar em próximos e não vistos. Sendo os próximos todos os vértices que tem conexão com algum vértice da árvore e os não vistos, o resto.
Empates são decididos arbitrariamente
Sempre há uma menor árvore de abrangência
Eficiência: Matriz com array não ordenada => |V²|. Lista de adjacência com mim-heap => |E| log |V|
Kruskal
Também é greedy (como Prim)
Menor árvore de abrangência por meio de subgrafos sempre acíclicos, mas não necessariamente conectados na fase intermediária do algoritmo.
Primeiramente, ordena as arestas em ordem crescente (de acordo com o peso)
Vai adicionando as arestas da lista em um subgrafo incialmente vazio
Se a aresta em questão criar um ciclo, ela é pulada
Ter que checar por ciclos aumenta o nível de complexidade
O algoritmo pode pegar os dois vértices que o vértice conecta e checar se estão em árvores diferentes. Sendo o caso,ok.
Há algoritmos eficientes para checar isso. Union-Find.
Eficiência (com Union-Find): |E| log |E|.
Um ciclo é criado quando dois vértices já conectados são novamente conectados. Forma-se uma árvore, não há ciclos.
Union-Find
ADT: Subconjuntos desarticulados
makeSet(x), find(x), union(x, y)
Quick find: array indexada, cujo valor é o conjunto a que pertence, mas a união ficaria em n², o ideal e adicionar o conjunto menor ao maior.
O tamanho de árvore pode ser dito pelo número de nós (union by size) ou pela altura (union by rank).
Tendo n-1 unions e m finds, eficiência: |n + m log n|