O algoritmo de Kruskal é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo conexo com pesos. Isto significa que ele encontra um subconjunto das arestas que forma uma árvore que inclui todos os vértices, onde o peso total, dado pela soma dos pesos das arestas da árvore, é minimizado. Se o grafo não for conexo, então ele encontra uma floresta geradora mínima (uma árvore geradora mínima para cada componente conexo do grafo). O algoritmo de Kruskal é um exemplo de um algoritmo guloso (também conhecido como ganancioso ou greedy).
Seu funcionamento é mostrado a seguir:
crie uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore separada crie um conjunto S contendo todas as arestas do grafo enquanto S for não-vazio, faça: remova uma aresta com peso mínimo de S se essa aresta conecta duas árvores diferentes, adicione-a à floresta, combinando duas árvores numa única árvore parcial do contrário, descarte a aresta
Ao fim do algoritmo, a floresta tem apenas um componente e forma uma árvore geradora mínima do grafo.
Com o uso de uma estrutura de dados eficiente, o algoritmo de Kruskal possui complexidade de tempo igual a O (m log n), onde m representa o número de arestas e n o número de vértices.
Exemplo 200px Grafo original a ser computado o algoritmo de Kruskal. Os números representam o peso nas arestas, e no momento não existe aresta selecionada. 200px As arestas AD e CE são as mais leves do grafo e ambas podem ser selecionadas. É escolhido ao acaso AD. 200px Agora a aresta CE é a mais leve. Já que ele não forma um laço com AD ela é selecionada. 200px A próxima aresta é a DF com peso 6. Ela não forma um laço com as arestas já selecionadas então ela é selecionada. 200px Agora duas arestas com peso 7 podem ser selecionadas e uma é escolhida ao acaso. A aresta BD é marcada pois forma um laço com as outras arestas já selecionadas. 200px Agora a outra aresta de peso 7 é selecionada pois cobre todos os requisitos de seleção. Similarmente ao passo anterior, outras arestas são marcadas para não serem selecionadas, pois resultariam em um laço. 200px Para finalizar é selecionada a aresta EG com peso 9. FG é marcada. Já que agora todas as arestas disponíveis formariam um laço, chega-se ao final do algoritmo e a árvore geradora mínima é encontrada.
Ver também Joseph Kruskal Algoritmo de Prim
Kruskal Categoria:Teoria dos grafos Kruskal Categoria:Árvores (teoria dos grafos)