Algoritmo de Borůvka

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde janeiro de 2014). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a consistência e o rigor deste artigo. Considere utilizar {{revisão-sobre}} para associar este artigo com um WikiProjeto e colocar uma explicação mais detalhada na discussão.

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[1] .

É 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. 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 orientado cuja representação matricial é a seguinte:

Exemplo 1
- 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: As posições (i,j) e (j,i) 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

Ver também[editar | editar código-fonte]

Referências

  1. GOODRICH, Michael T.; TAMASSIA, Roberto. Projeto de Algoritmos: Fundamentos, Análise e Exemplos da Internet. Porto Alegre: Bookman, 2004. p. 369-370. ISBN 85-363-0303-4.