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

Gildásio Guedes Fernandes Antonella Maria das Chagas Sousa Fabiana Rodrigues de Almeida Castro Maria da Conceição Prado de Oliveira Zoraida Maria Lopes Feitosa Miguel Arcanjo Costa José Vanderlei Carneiro Lívia Fernanda Nery da Silva João Benício de Melo Neto Vera Lúcia Costa Oliveira Milton Batista da Silva Leonardo Ramon Nunes de Sousa CONSELHO EDITORIAL DA EDUFPI Prof. Dr. Ricardo Alaggio Ribeiro ( Presidente ) Des. Tomaz Gomes Campelo Prof. Dr. José Renato de Araújo Sousa Profª.…