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

Animação do funcionamento do Algoritmo de Boruvka.

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