15

Os dois algoritmos servem para gerar uma Árvore Geradora Mínima de um Grafo.

No Prim

  • Gera uma árvore única
  • Ao longo do algoritmo, o conjunto X sempre é uma árvore

No Kruskal

  • Gera uma floresta, antes de gerar uma Árvore Geradora Mínima
  • Existe garantia de ser apenas uma árvore apenas depois da última iteração

Mas a dúvida maior é:

Qual seria a Vantagem e Desvantagem entre eles?


Informações complementares

  • Algoritmo de Dijkstra soluciona o problema do caminho mais curto num grafo.
  • Algoritmo de Dijkstra e Prim são quase exatamente iguais, porém no Prim você não soma o resultado obtido, mas a execução é igual.
  • A utilização desses dois algoritmos são para problemas distintos (não são relacionados ao mesmo problema). Um resolve o caminho mais curto enquanto o outro gera uma AGM.
2

1 Resposta 1

8
+50

Algumas diferenças entre os algoritmos:

  • O algoritmo de Prim inicializa com um nó, enquanto o algoritmo de Kruskal inicia com uma aresta ordenada.

  • No algoritmo de Prim, o grafo deve ser conectado, enquanto o Kruskal pode funcionar em grafos desconectados também.

  • A complexidade do algoritmo de Prim em implementações mais comuns para um grafo são por listas de adjacência e por matrizes de adjacência e suas respectivas complexidades O(|A|log|V|) e O(V^2) no pior caso. E o algoritmo de Kruskal possui complexidade de tempo igual a O(m log n), onde m representa o número de arestas e n o número de vértices.

Nessa resposta do stackoverflow, tem uma comparação interessante:

Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.

O algoritmo de Prim é significativamente mais rápido no limite quando você tem um gráfico realmente denso com muitas mais arestas do que vértices. Kruskal funciona melhor em situações típicas (gráficos esparsos) porque usa estruturas de dados mais simples.

Sobre as vantagens e desvantagens:

  • Ambos são simples e encontram uma boa solução para o problema, sendo que na maioria das vezes é a solução ótima.

  • Se pararmos o algoritmo no meio, no algoritmo de Prim sempre será gerado uma árvore conectada. Já no Kruskal, pode ser uma árvore ou floresta desconectada.


Referências:

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .