Algoritmo de kruskal

Algoritmo de Kruskal Apresentado em 1956 e desenvolvido por Joseph Bernard Kruskal Jr., o algoritmo de Kruskal, é um algoritmo para manipulação com grafos que busca formar uma árvore geradora mínima (alguns casos são formadas florestas) a partir de um grafo valorado que pode ser representado também por uma matriz de adjacência que represente as arestas valoradas como veremos abaixo. Esse tipo de algoritmo é conhecido também como um algoritmo guloso por que é usado para resolver problemas de otimização, encontrar o caminho mais curto entre dois vértices, dois nós diferentes.

Tarefas e Objetivo

O objetivo do algoritmo de Kruskal é determinar o caminho menor para alcançar o ponto final Y a partir do ponto de partida X em um grafo valorado, mas para isso tem de existir primeiramente a determinação de uma árvore geradora para esse mesmo grafo valorado. Para isso cada aresta há de ter um ‘peso’, que na maioria dos softwares é a distância entre um ponto e outro. Após saber que cada aresta há de ter seu peso e um problema terá N pontos (nós) a serem percorridos, esses dados provavelmente estarão armazenados em uma matriz de adjacência com o peso de cada aresta representando, portanto, um grafo. Resta saber o que Kruskal fez para ‘viajar’ de X até Y pelo menor caminho, pois bem, a ideia de Kruskal é passar por todos os nós do grafo.

Grafo a partir da matriz acima:

Matriz de adjacência: A B C D E F A 0 3 1 3 2 2 B 3 0 2 0 0 4 C 1 2 0 2 0 0 D 3 0 2 0 3 0 E 2 0 0 3 0 2 F 2 4 0 0 2 0

Uma observação importante é que para um grafo conexo será gerada uma única árvore (árvore geradora mínima), e para um grafo não conexo (desconexo), será formada um conjunto de árvores, sendo uma para cada subgrafo do grafo desconexo, será gerada uma árvore formando assim uma floresta (floresta geradora mínima). O algoritmo de Kruskal também visa a não existência de ciclos, pois