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 miniaturadaimagem|339x339px|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) FIMAqui, 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
Categoria:Teoria dos grafos Boruvka Categoria:Árvores (teoria dos grafos)