Algoritmo de Spanning Tree de Kruskal

O algoritmo de Kruskal para encontrar a árvore geradora de custo mínimo usa a abordagem gananciosa. Este algoritmo trata o gráfico como uma floresta e cada nó que ele possui como uma árvore individual. Uma árvore se conecta a outra somente e somente se ela tiver o menor custo entre todas as opções disponíveis e não violar as propriedades do MST.

Para entender o algoritmo de Kruskal, vamos considerar o seguinte 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 - Organize todas as arestas em sua ordem crescente de peso

A próxima etapa é criar um conjunto de arestas e peso e organizá-los em uma ordem crescente de peso (custo).

Passo 3 - Adicione a aresta que tem o menor peso

Agora começamos a adicionar arestas ao gráfico, começando pela que tem menos peso. Durante todo o processo, continuaremos verificando se as propriedades de abrangência permanecem intactas. No caso, ao adicionar uma aresta, a propriedade de spanning tree não é válida, então devemos considerar não incluir a aresta no gráfico.

O menor custo é 2 e as arestas envolvidas são B, D e D, T. Nós os adicionamos. Adicioná-los não viola as propriedades da árvore estendida, portanto, continuamos com nossa próxima seleção de aresta.

O próximo custo é 3, e as arestas associadas são A, C e C, D. Nós os adicionamos novamente -

O próximo custo na tabela é 4, e observamos que adicioná-lo criará um circuito no gráfico. -

Nós o ignoramos. No processo, devemos ignorar / evitar todas as arestas que criam um circuito.

Observamos que arestas com custo 5 e 6 também criam circuitos. Nós os ignoramos e seguimos em frente.

Agora resta apenas um nó a ser adicionado. Entre as duas arestas de menor custo disponíveis 7 e 8, devemos adicionar a aresta com custo 7.

Ao adicionar a aresta S, A, incluímos todos os nós do gráfico e agora temos a árvore geradora de custo mínimo.