Algoritmo de kruskal

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (727 palavras )
  • Download(s) : 0
  • Publicado : 5 de abril de 2013
Ler documento completo
Amostra do texto
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 geradoramí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 tipode 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 eObjetivo

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 primeiramentea 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 quecada 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 00 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...
tracking img