Diferença entre Kruskal e Prim

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 gráfico não direcionado ponderado conectado. Uma árvore de abrangência é um subgráfico de um gráfico, de modo que cada nó do gráfico seja conectado por um caminho, que é uma árvore. Cada árvore de abrangência tem um peso e os pesos / custos mínimos possíveis de todas as árvores de abrangência são a árvore de abrangência mínima (MST).

Mais sobre o algoritmo de Prim

O algoritmo foi desenvolvido pelo matemático tcheco Vojtěch Jarník em 1930 e posteriormente de forma independente pelo cientista da computação Robert C. Prim em 1957. Foi redescoberto por Edsger Dijkstra em 1959. O algoritmo pode ser declarado em três etapas principais;

Dado o gráfico conectado com n nós e o peso respectivo de cada aresta,

1. Selecione um nó arbitrário no 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 a partir desse nó em 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²).

Mais sobre o algoritmo de Kruskal

O algoritmo desenvolvido por Joseph Kruskal apareceu nos procedimentos da Sociedade Americana de Matemática 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 o peso respectivo de cada aresta,

1. Selecione o arco com o menor peso do gráfico inteiro e adicione à árvore e exclua do gráfico.

2. Do restante, 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.

Nesse método, o algoritmo começa com a borda com menor peso e continua selecionando cada borda em cada ciclo. Portanto, no algoritmo, o gráfico não precisa estar conectado. O algoritmo de Kruskal possui uma complexidade temporal de O (logV)

Qual é a diferença entre o algoritmo de Kruskal e o de Prim?

• O algoritmo de Prim é inicializado com um nó, enquanto o algoritmo de Kruskal inicia com uma borda.

• Os algoritmos de Prim abrangem um nó para outro, enquanto o algoritmo de Kruskal seleciona as arestas de uma maneira que a posição da aresta não se baseia na última etapa.

• No algoritmo de prim, o gráfico deve ser um gráfico conectado, enquanto o Kruskal também pode funcionar em gráficos desconectados.

• O algoritmo de Prim possui uma complexidade de tempo de O (V²) e a complexidade de tempo de Kruskal é O (logV).