Algoritmo de Borůvka
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif/339px-Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif)
O 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
O 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
Grafo | Componente | Descrição |
---|---|---|
![]() | {A} {B} {C} {D} {E} {F} {G} | Esse é nosso grafo original. Observe que cada nó é, por si só, um único componente. No Pseudocódigo, ao utilizar UNION-FIND, definimos que o líder de cada nó será o próprio nó. No início, nossa floresta F terá sete componentes (F = 7). |
![]() | {A,B,D,F} {C,E,G} | No primeiro passo, o algoritmo irá checar cada nó e selecionar a aresta de menor custo para aquele nó, mesmo que essa aresta já tenha sido selecionada. Observe que, ao terminarmos esse processo, teremos dois componentes tal que não há nada conectando-os (são não-conexos) e nossa floresta F está com dois componentes (F = 2), então o laço continua rodando. |
![]() | {A,B,C,D,E,F,G} | Agora, no segundo passo, o algoritmo irá verificar a menor aresta disponível entre os componentes e irá selecionar-la, conectando os mesmo e, portanto, deixando F = 1. Agora o laço está completo. |
Ver também
- Otakar Borůvka
- Algoritmo de Prim
- Algoritmo de Kruskal
Referê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 !CS1 manut: Nomes múltiplos: lista de autores (link)