Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's & Kruskal's Algorithm - Coggle Diagram
Prim's & Kruskal's Algorithm
Algoritmos gananciosos:
constroem uma solução por meio de uma sequência de etapas, cada uma expandindo uma solução parcialmente construída
MST:
Uma árvore geradora T de G é mínima se nenhuma outra árvore geradora tem custo menor que o de T. Árvores geradoras mínimas também são conhecidas pela abreviatura MST de minimum spanning tree
Uma MST soluciona problemas em que dado um grafo não-dirigido com custos nas arestas, encontra uma árvore geradora mínima do grafo
Prim :
Faz crescer uma árvore até que ela se torne geradora (MST)
Implementação :
Atribuir um valor-chave a todos os vértices no gráfico de entrada. Inicializar todos os valores-chave como INFINITO. Atribuir para o primeiro vértice o valor 0 para que seja escolhido primeiro
Enquanto mstSet não inclui todos os vértices :
escolher
um vértice
u
que não está na mstSet e tem um valor de chave mínimo;
incluir
u
na mstSet;
atualizar
o valor da chave de todos os vértices adjacentes de u.
Criar um set mstSet que monitora os vértices já incluídos no MST
:warning: Obs: Melhor para grafos densos
Kruskal :
Faz crescer uma floresta geradora até que ela se torne uma árvore (MST)
Implementação :
Escolher a menor aresta e verificar se forma um ciclo com a árvore geradora formada até o momento. Se o ciclo não for formado, incluir esta aresta. Caso contrário, descarte-a
Repetir a etapa 2 até que haja (V-1) arestas na árvore geradora
Classificar todas as arestas em ordem não decrescente de seu peso
:warning: Obs: Melhor para grafos espaçados
Complexidade :
Matrix sem heap : Θ(|V|^2)
Lista com heap : Θ((|V|+|E|) log|V|)
Θ((|V|+|E|) log|V|)