Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal - Coggle Diagram
Algoritmo de Prim
Eficiência
Matriz + array desordenado = (-) (V^2)
Matriz + min-heap = O(|E| log |V |)
Aplicação
O caminho que liga n pontos da forma mais "barata"
Gera
Mininum Spanning tree
Algoritmo do tipo greedy
Ele "cresce" dentro do grafo
Algoritmo de Kruskal
algoritmos de unionfind
Operações
MakeSet
Union
By size / By rank melhora o pior caso
Implementações
Quick find
Quick union
Gera
Minimum Spanning tree
Aplicação
A mesma do de prim
Sorting de arestas
Scaneia a lista incluindo as arestas à arvore caso elas não formem ciclos
Eficiência
O(|E| log |E|)
Funcionamento