Diferença Entre Kruskal E Prim

2024 Autor: Mildred Bawerman | [email protected]. Última modificação: 2023-12-16 08:41

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 ²).

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 ²), e a complexidade de tempo de Kruskal é O (logV).