Algoritmo de Boruvka

Origem: Wikipédia, a enciclopédia livre.

Dado um grafo, representado sob qualquer uma das suas possíveis representações (embora a mais comum seja a forma matricial), o algoritmo de Boruvka (ou Baruvka como também é conhecido) consiste, tal como o algoritmo da Minimum Spanning Tree (árvore geradora mínima) de Dijkstra, em encontrar a mínima distância entre todos os pontos do grafo.

Este algoritmo caracteriza-se pela divisão do grafo original em vários subgrafos para os quais é calculado a Minimum Spanning Tree. Ou seja, no fundo, pode ser considerada uma variação do algoritmo original de Dijkstra.

É um algoritmo com uma velocidade de convergência (ou resolução) bastante rápida sendo ideal para implementação em computadores paralelos já que a Minimum Spanning Tree de cada um dos subgrafos pode ser calculada numa máquina diferente.

Este algoritmo é recursivo e só termina quando existe apenas um vértice.

O algoritmo de Baruvka compreende os seguintes passos:

1 - para cada vértice escolher o seu arco com peso mínimo. Este passo, deste passo poderão resultar vários subgrafos

2 - caso o passo 1 dê origem a grafos não conectados, considere-se cada subgrafo gerado no passo anterior como um vértice do grafo final. Estes vértices do grafo final conterão os vértices de cada umdos subgrafos gerados no passo 1. Para cada um dos subgrafos gerados execute-se de novo o passo 1 (recursividade). Neste momento pode-se, caso existam várias máquinas diferentes, correr este algoritmo nas várias máquinas sendo que cada máquina irá ter assignada a si um dos subgrafos gerados no passo 1 (este tipo de distribuição de processamento é mais conhecido como Single Instruction Multiple Data já que cada máquina vai executar as mesmas instruções mas sobre um conjunto de dados diferentes).

3 - Quando for encontrada a Minimum Spanning Tree para cada um dos grafos gerar um novo grafo onde cada um vértices deste grafo é um dos subgrafos. O objectivo agora será voltar a executar os passos 1 a 3 até que existam apenas 2 vértices e um único arco.

A título de exemplo

Seja V um grafo não grafo orientado cuja representação matricial é a seguinte

   a  b  c  d  e  f

a 0 4 2 0 0 0 b 4 0 2 0 5 1 c 2 2 0 10 1 0 d 0 0 10 0 15 0 e 0 5 1 15 0 2 f 0 1 0 0 2 0

Nota: A posição (1,2) e (2,1), por exemplo, da matriz anterior têm os mesmos valores. Isso indica que o grafo em análise é não orientado.

Executando o passo 1 acima referido sobre esta matriz passaríamos a ter a seguinte matriz

   a  b  c  d  e  f

a 0 0 2 0 0 0 b 0 0 0 0 0 1 c 0 0 0 0 1 0 d 0 0 10 0 0 0 e 0 0 0 0 0 0 f 0 0 0 0 0 0

Analisando esta nova matriz podemos ver que existem duas linhas a zero (e e f), o que claramente indica a existência de dois subgrafos. Como verificar quais os subgrafos? É um processo simples de verificar quais as linhas e colunas que se cruzam. Neste caso os novos subgrafos são dados pelas seguintes matrizes:

   b  f

b 0 1 f 0 0

   a  c  d  e

a 0 2 0 0 c 0 0 0 1 d 0 10 0 0 e 0 0 0 0

Notar que é necessário reter,da matriz original os valores que cruzam os vértices dos diferentes subgrafos gerados no passo 1, ou seja, a arco a-b (com peso 4), o arco c-b (com peso 2), o arco b-e (com peso 5) e o arco e-f (com peso 2). Estes arcos são usados para unir os vértices do arco gerado no passo 3.

Neste exemplo bastante simples, o passo 2 representado pelas duas matrizes anteriores. Deste modo, não é necessário encontrar a Minimum Spanning Tree para cada uma destas matrizes já que quando se executa o passo 1 estas são encontradas automaticamente (outros exemplos há em que é necessário executar o passo 2). Isto leva, então, à geração do grafo do passo 3 em que temos dois vértices (um para cada uma das matrizes anteriores) e que pode ser representado sob a seguinte forma

      bf       acde

bf 0 4/2/2/5 acde 4/2/2/5 0

Note-se que a diagonal principal da matriz está a zero mas a outra diagonal não (é apenas uma questão de representacão. (matriz transposta esta matriz ir-se-ia obter a diagonal principal não nula e a outra diagonal a zero.) Estes valores indicam possíveis arcos que ligam os vértices deste grafo. Então, volta-se a executar o passo 1 sobre este grafo pelo que se chega à conclusão de que o grafo inicial deu origem a um grafo final cuja representação é a seguinte

      bf  acde

bf 0 2 acde 0 0

Ilustração gráfica do exemplo anterior em construção