Algoritmo de Borůvka

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.

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.