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.