Algoritmo de Spanning Tree de Prim

O algoritmo de Prim para encontrar a árvore geradora de custo mínimo (como o algoritmo de Kruskal) usa a abordagem gananciosa. O algoritmo de Prim compartilha uma semelhança com oshortest path first algoritmos.

O algoritmo de Prim, em contraste com o algoritmo de Kruskal, trata os nós como uma única árvore e continua adicionando novos nós à árvore geradora a partir do grafo dado.

Para contrastar com o algoritmo de Kruskal e entender melhor o algoritmo de Prim, devemos usar o mesmo exemplo -

Etapa 1 - Remova todos os loops e bordas paralelas

Remova todos os loops e bordas paralelas do gráfico fornecido. No caso de bordas paralelas, mantenha a de menor custo associada e remova todas as demais.

Etapa 2 - Escolha qualquer nó arbitrário como nó raiz

Neste caso, nós escolhemos Snó como o nó raiz da árvore de abrangência de Prim. Este nó é escolhido arbitrariamente, portanto, qualquer nó pode ser o nó raiz. Alguém pode se perguntar por que qualquer vídeo pode ser um nó raiz. Portanto, a resposta é: na árvore de abrangência todos os nós de um gráfico estão incluídos e, como ele está conectado, deve haver pelo menos uma aresta, que o unirá ao resto da árvore.

Etapa 3 - Verifique as bordas de saída e selecione aquela com menor custo

Depois de escolher o nó raiz S, vemos que S, A e S, C são duas arestas com peso 7 e 8, respectivamente. Escolhemos a aresta S, A porque é menor que a outra.

Agora, a árvore S-7-A é tratada como um nó e verificamos se há todas as arestas saindo dela. Selecionamos aquele de menor custo e incluímos na árvore.

Após esta etapa, a árvore S-7-A-3-C é formada. Agora vamos tratá-lo novamente como um nó e verificar todas as arestas novamente. No entanto, escolheremos apenas a margem de menor custo. Neste caso, C-3-D é a nova aresta, que é menor que o custo de outras arestas 8, 6, 4, etc.

Depois de adicionar o nó Dpara a árvore geradora, agora temos duas arestas saindo dela com o mesmo custo, ou seja, D-2-T e D-2-B. Assim, podemos adicionar qualquer um. Mas a próxima etapa resultará novamente na borda 2 como o menor custo. Portanto, estamos mostrando uma árvore de abrangência com ambas as arestas incluídas.

Podemos descobrir que a árvore geradora de saída do mesmo gráfico usando dois algoritmos diferentes é a mesma.