Kruskal vs Prim
Na ciência da computação, os algoritmos de Prim e Kruskal são um algoritmo ganancioso que encontra uma árvore de abrangência mínima para um grafo não direcionado ponderado conectado. Uma árvore estendida é um subgráfico de um gráfico de forma que cada nó do gráfico seja conectado por um caminho, que é uma árvore. Cada árvore geradora tem um peso, e os pesos / custos mínimos possíveis de todas as árvores abrangentes são 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. Ele foi redescoberto por Edsger Dijkstra em 1959. O algoritmo pode ser declarado em três etapas principais;
Dado o grafo conectado com n nós e 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 gráfico. (Selecione qualquer um se houver dois ou mais mínimos)
3. Repita a etapa 2, até que n-1 arestas sejam adicionadas à árvore.
Nesse método, a árvore começa com um único nó arbitrário e se expande desse nó em diante a cada ciclo. Portanto, para que o algoritmo funcione corretamente, o gráfico precisa ser um gráfico conectado. A forma básica do algoritmo de Prim tem uma complexidade de tempo de O (V 2).
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 gráfico com n nós e 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. Das restantes, selecione a aresta menos ponderada, de forma a não formar um ciclo. Adicione a aresta à árvore e exclua do gráfico. (Selecione qualquer um se houver dois ou mais mínimos)
3. Repita o processo na etapa 2.
Neste método, o algoritmo começa com a aresta menos ponderada e continua selecionando cada aresta em cada ciclo. Portanto, no algoritmo, o gráfico não precisa ser conectado. O algoritmo de Kruskal tem uma complexidade de tempo de O (logV)
Qual é a diferença entre o algoritmo de Kruskal e o algoritmo 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 na última etapa.
• No algoritmo de prim, o gráfico deve ser um gráfico conectado enquanto o de Kruskal também pode funcionar em gráficos desconectados.
• O algoritmo de Prim tem uma complexidade de tempo O (V 2), e a complexidade de tempo de Kruskal é O (logV).
