Algoritmo de Borůvka
# 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
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.
É 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

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:
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

| 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. |