Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal - Coggle Diagram
Algoritmo de Prim
eficiência
se o grafo for representado por uma lista e a fila de prioridade for implementada como uma min-heap, a eficiência do algoritmo é Ohm(|E| log|V|)
se o grafo for representado por uma matriz e a fila de prioridade implementada como array desordenado, a eficiência do algoritmo é Theta(|V|²)
-
-
-
-
Algoritmo de Kruskal
algoritmos busca-união
busca rápida
-
usa um array indexado pelos elementos do conjunto, onde os valores do array indicam o representante do sobconjunto
cada subconjunto é implementado como uma lista ligada, cujo header possui ponteiros para o primeiro e último elementos e o número de elementos na lista
eficiência
-
-
operação union(x,y) em Theta(n²)
-
união rápida
-
-
eficiência
operação union(x,y) em Theta(1)
-
-
-
-
retorna apenas um subgrafo acíclico, não uma árvore
com um algoritmo busca-união eficiente, o tempo de execução depende da ordenação e, com um algoritmo de ordenação eficiente, o tempo de execução fica em Ohm(|E| log|E|)
-