Algoritmo de Borůvka
O algoritmo de Minimum Spanning Tree não é de Dijkstra foi marcada para revisão devido a incoerências ou dados de confiabilidade duvidosa. |
O Algoritmo de Borůvka (ou Barůvka como também é conhecido) é um algoritmo para encontrar uma árvore geradora mínima em um grafo para o qual todos os pesos de arestas sejam distintos[1]
Este algoritmo caracteriza-se pela divisão do grafo original em vários subgrafos para os quais é calculado a Minimum Spanning Tree (árvore geradora mínima). Ou seja, no fundo, pode ser considerada uma variação de algoritmos como os de Prim e Kruskal. É um algoritmo que, de modo diverso dos algoritmos de Kruskal e Prim, não usa uma fila de prioridades[2].
É um algoritmo com uma velocidade de convergência (ou resolução) bastante rápida. A implementação desse algoritmo pode ser feita de forma recursiva e só termina quando existe apenas um vértice.
Funcionamento
editarO algoritmo de Boruvka compreende os seguintes passos:
1 - Para cada vértice, escolher o sua aresta de menor custo. Deste passo poderão resultar um ou mais subgrafos.
2 - Caso o passo 1 dê origem a grafos não conectados, considere cada subgrafo gerado no passo anterior como um vértice do grafo final. Então, repita o primeiro passo, encarando cada subgrafo como se fosse um vértice e olhando para as arestas entre esses subgrafos.
Observe na imagem sobre o funcionamento do algoritmo que, primeiramente, o mesmo vai, nó a nó (neste exemplo, em ordem alfabética), verificando qual a menor aresta relacionada ao dado nó. Em seguida, ao verificar todos os nós, temos uma série de componentes não conexos. Então o algoritmo verifica todos esses componente e acha qual a menor aresta relacionada aquele componente.
Pseudo-código
editarO Seguinte pseudo-código para o Algoritmo de Boruvka utiliza Union-Find:
ALGORITMO BORUVKA(G)
Crie uma floresta F com cada nó do grafo
Crie um vetor de LIDER com todos os nós
para cada nó u em G
LIDER[u] = u
Enquanto F > 1 faça
para cada componente c em G
ache a aresta cv de menor custo
se FIND(c, LIDER) diferente de FIND(v, LIDER) então
adicione cv a F
UNION(c, v)
FIM
Aqui, o "componente c" é, a princípio, cada nó u do grafo. Nós chamamos de "componente" e não de "nó" pois, ao unir um certo número de nós (passo 1), podemos ter dois subgrafos não-conexos e nenhum outro nó livre, como no passo 2 (observe que, neste ponto, o número de elementos em F é 2). Logo, o algoritmo de Boruvka irá continuar o laço "enquanto". Então o próximo passo é selecionar as arestas entre os dois componentes (sub-grafos) restantes e selecionar a menor dentre elas, unindo-os. Agora o número de componentes em F é 1 e o laço termina.
Exemplo
editarVer também
editarReferências
- ↑ Feofiloff, Paulo (7 de julho de 2015). «Algoritmo de Boruvka». IME USP - Instituto de Matemática e estatística da Universidade de São Paulo. Consultado em 20 de novembro de 2018
- ↑ GOODRICH, Michael T.; TAMASSIA, Roberto (2004). Projeto de Algoritmos. Fundamentos, Análise e Exemplos da Internet. Porto Alegre: Bookman. p. 369-370. ISBN 85-363-0303-4