Algoritmo de Kruskal

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde janeiro de 2014).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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 aceitável, o algoritmo de Kruskal pode ser demonstrado que executa em tempo O (m log n), onde m é o número de arestas e n o número de vértices.

Exemplo[editar | editar código-fonte]

Prim Algorithm 0.svg 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.
Kruskal Algorithm 1.svg As arestas AD e CE são as mais leves do grafo e ambas podem ser selecionadas. É escolhido ao acaso AD.
Kruskal Algorithm 2.svg Agora a aresta CE é a mais leve. Já que ele não forma um laço com AD ela é selecionada.
Kruskal Algorithm 3.svg 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.
Kruskal Algorithm 4.svg 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.
Kruskal Algorithm 5.svg 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.
Kruskal Algorithm 6.svg 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[editar | editar código-fonte]