Kruskal vs Prim
Em ciência da computação, os algoritmos de Prim e Kruskal são um algoritmo ganancioso que encontra uma árvore geradora mínima para um grafo não direcionado ponderado conectado. Uma árvore geradora é um subgrafo de um grafo tal que cada nó do grafo é conectado por um caminho, que é uma árvore. Cada árvore geradora tem um peso, e o peso/custo mínimo possível de todas as árvores geradoras é a árvore geradora mínima (MST).
Mais sobre o Algoritmo de Prim
O algoritmo foi desenvolvido pelo matemático tcheco Vojtěch Jarník em 1930 e mais tarde independentemente pelo cientista da computação Robert C. Prim em 1957. Foi redescoberto por Edsger Dijkstra em 1959. O algoritmo pode ser enunciado em três etapas principais;
Dado o grafo conectado com n nós e o respectivo peso de cada aresta, 1. Selecione um nó arbitrário do gráfico e adicione-o à árvore T (que será o primeiro nó)
2. Considere os pesos de cada aresta conectada aos nós da árvore e selecione o mínimo. Adicione a aresta e o nó na outra extremidade da árvore T e remova a aresta do grafo. (Selecione qualquer se existirem dois ou mais mínimos)
3. Repita o passo 2, até que n-1 arestas sejam adicionadas à árvore.
Neste método, a árvore começa com um único nó arbitrário e se expande a partir desse nó a cada ciclo. Portanto, para que o algoritmo funcione corretamente, o grafo precisa ser um grafo conectado. A forma básica do algoritmo de Prim tem uma complexidade de tempo de O(V2).
Mais sobre o Algoritmo de Kruskal
O algoritmo desenvolvido por Joseph Kruskal apareceu nos anais da American Mathematical Society em 1956. O algoritmo de Kruskal também pode ser expresso em três etapas simples.
Dado o grafo com n nós e o respectivo peso de cada aresta, 1. Selecione o arco com o menor peso de todo o gráfico e adicione à árvore e exclua do gráfico.
2. Dos restantes selecione a aresta de menor peso, de forma que não forme um ciclo. Adicione a aresta à árvore e exclua do gráfico. (Selecione qualquer se existirem dois ou mais mínimos)
3. Repita o processo na etapa 2.
Neste método, o algoritmo começa com a aresta de menor peso e continua selecionando cada aresta em cada ciclo. Portanto, no algoritmo o grafo não precisa ser conectado. O algoritmo de Kruskal tem complexidade de tempo O(logV)
Qual é a diferença entre o Algoritmo de Kruskal e o de Prim?
• O algoritmo de Prim inicializa com um nó, enquanto o algoritmo de Kruskal inicia com uma aresta.
• Os algoritmos de Prim vão de um nó a outro enquanto o algoritmo de Kruskal seleciona as arestas de forma que a posição da aresta não seja baseada no último passo.
• No algoritmo do prim, o grafo deve ser um grafo conectado enquanto o Kruskal também pode funcionar em grafos desconectados.
• O algoritmo de Prim tem uma complexidade de tempo O(V2), e a complexidade de tempo de Kruskal é O(logV).
