Algoritmo de Borůvka - Borůvka's algorithm

Animação do algoritmo de Boruvka

O algoritmo de Borůvka é um algoritmo ganancioso para encontrar uma árvore geradora mínima em um gráfico, ou uma floresta geradora mínima no caso de um gráfico que não está conectado.

Foi publicado pela primeira vez em 1926 por Otakar Borůvka como um método de construção de uma rede elétrica eficiente para a Morávia . O algoritmo foi redescoberto por Choquet em 1938; novamente por Florek , Łukasiewicz , Perkal , Steinhaus e Zubrzycki em 1951; e novamente por Georges Sollin em 1965. Esse algoritmo é freqüentemente chamado de algoritmo de Sollin , especialmente na literatura de computação paralela .

O algoritmo começa encontrando a aresta de peso mínimo incidente em cada vértice do gráfico e adicionando todas essas arestas à floresta. Em seguida, ele repete um processo semelhante de encontrar a aresta de peso mínimo de cada árvore construída até agora em uma árvore diferente e adicionar todas essas arestas à floresta. Cada repetição desse processo reduz o número de árvores, dentro de cada componente conectado do gráfico, para no máximo a metade desse valor anterior, portanto, após logaritmicamente muitas repetições, o processo termina. Quando isso acontece, o conjunto de arestas que ele adicionou forma a floresta de extensão mínima.

Pseudo-código

O pseudocódigo a seguir ilustra uma implementação básica do algoritmo de Borůvka. Nas cláusulas condicionais, toda aresta uv é considerada mais barata do que "Nenhuma". O objetivo da variável concluída é determinar se a floresta F ainda é uma floresta abrangente.

Se as arestas não tiverem pesos distintos, uma regra de desempate consistente deve ser usada, por exemplo, com base em alguma ordem total de vértices ou arestas. Isso pode ser obtido representando vértices como inteiros e comparando-os diretamente; comparar seus endereços de memória ; etc. Uma regra de desempate é necessária para garantir que o grafo criado seja de fato uma floresta, ou seja, não contenha ciclos. Por exemplo, considere um gráfico de triângulo com nós { a , b , c } e todas as arestas de peso 1. Em seguida, um ciclo poderia ser criado se selecionarmos ab como a aresta de peso mínimo para { a }, bc para { b }, e ca para { c }. Uma regra de desempate que ordena as bordas primeiro por origem, depois por destino, impedirá a criação de um ciclo, resultando na árvore de abrangência mínima { ab , bc }.

algorithm Borůvka is
    input: A weighted undirected graph G = (V, E).
    output: F, a minimum spanning forest of G.

    Initialize a forest F to (V, E') where E' = {}.

    completed := false
    while not completed do
        Find the connected components of F and assign to each vertex its component
        Initialize the cheapest edge for each component to "None"
        for each edge uv in E, where u and v are in different components of F:
            let wx be the cheapest edge for the component of u
            if is-preferred-over(uv, wx) then
                Set uv as the cheapest edge for the component of u
            let yz be the cheapest edge for the component of v
            if is-preferred-over(uv, yz) then
                Set uv as the cheapest edge for the component of v
        if all components have cheapest edge set to "None" then
            // no more trees can be merged -- we are finished
            completed := true
        else
            completed := false
            for each component whose cheapest edge is not "None" do
                Add its cheapest edge to E'

function is-preferred-over(edge1, edge2) is
    return (edge1 is "None") or
           (weight(edge1) < weight(edge2)) or
           (weight(edge1) = weight(edge2) and tie-breaking-rule(edge1, edge2))

function tie-breaking-rule(edge1, edge2) is
    The tie-breaking rule; returns true if and only if edge1
    is preferred over edge2 in the case of a tie.

Como uma otimização, pode-se remover de G cada aresta que se encontra conectando dois vértices em um mesmo componente, de forma que não contribua no tempo de busca por arestas mais baratas em componentes posteriores.

Complexidade

O algoritmo de Borůvka pode ser mostrado para tomar O (log V ) iterações do loop externo até que ele termine e, portanto, executar no tempo O ( E log V ), onde E é o número de arestas e V é o número de vértices em G (assumindo EV ). Em gráficos planares , e mais geralmente em famílias de gráficos fechados em operações menores de gráfico , ele pode ser executado em tempo linear, removendo tudo, exceto a aresta mais barata entre cada par de componentes após cada estágio do algoritmo.

Exemplo

Imagem componentes Descrição
Borůvka Algorithm 1.svg {A}
{B}
{C}
{D}
{E}
{F}
{G}
Este é nosso gráfico ponderado original. Os números próximos às bordas indicam seu peso. Inicialmente, cada vértice por si só é um componente (círculos azuis).
Borůvka Algorithm 2.svg {A, B, D, F}
{C, E, G}
Na primeira iteração do loop externo, a borda de peso mínimo de cada componente é adicionada. Algumas arestas são selecionadas duas vezes (AD, CE). Dois componentes permanecem.
Borůvka Algorithm 3.svg {ABCDEFG} Na segunda e última iteração, a borda de peso mínimo de cada um dos dois componentes restantes é adicionada. Acontece que são a mesma borda. Resta um componente e pronto. A borda BD não é considerada porque os dois pontos finais estão no mesmo componente.

Outros algoritmos

Outros algoritmos para este problema incluem o algoritmo de Prim e Algoritmo de Kruskal . Algoritmos paralelos rápidos podem ser obtidos combinando o algoritmo de Prim com o de Borůvka.

Um algoritmo de árvore geradora mínima aleatório mais rápido baseado em parte no algoritmo de Borůvka devido a Karger, Klein e Tarjan é executado no tempo O ( E ) esperado . O algoritmo de spanning tree mínimo (determinístico) mais conhecido de Bernard Chazelle também é baseado em parte no de Borůvka e é executado no tempo O ( E α ( E , V )) , onde α é o inverso da função de Ackermann . Esses algoritmos aleatórios e determinísticos combinam etapas do algoritmo de Borůvka, reduzindo o número de componentes que permanecem para serem conectados, com etapas de um tipo diferente que reduzem o número de arestas entre pares de componentes.

Notas

  1. ^ Borůvka, Otakar (1926). "O jistém problemaému minimálním" [Sobre um certo problema mínimo]. Práce Mor. Přírodověd. Spol. V Brně III (em tcheco e alemão). 3 : 37–58.
  2. ^ Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodníchreenshotí (Contribuição para a solução de um problema de construção económica de redes eléctricas)". Elektronický Obzor (em tcheco). 15 : 153–154.
  3. ^ Nešetřil, Jaroslav ; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka no problema da árvore geradora mínima: tradução de ambos os documentos de 1926, comentários, história". Discrete Mathematics . 233 (1–3): 3–36. doi : 10.1016 / S0012-365X (00) 00224-7 . hdl : 10338.dmlcz / 500413 . MR  1825599 .
  4. ^ Choquet, Gustave (1938). "Étude de sures réseaux de routes". Comptes Rendus de l'Académie des Sciences (em francês). 206 : 310–313.
  5. ^ Florek, K .; Łukaszewicz, J .; Perkal, J .; Steinhaus, Hugo ; Zubrzycki, S. (1951). "Sur la liaison et la division des points d'un ensemble fini" . Colloquium Mathematicae (em francês). 2 : 282–285. MR  0048832 .
  6. ^ Sollin, Georges (1965). "Le tracé de canalisation". Programação, jogos e redes de transporte (em francês).
  7. ^ Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R. ; Urrutia, J. (eds.). Handbook of Computational Geometry . Elsevier. pp. 425–461.; Mareš, Martin (2004). "Dois algoritmos de tempo linear para MST em classes de grafos fechados menores" (PDF) . Archivum Mathematicum . 40 (3): 315–320..
  8. ^ Bader, David A .; Cong, Guojing (2006). "Algoritmos de memória compartilhada rápidos para calcular a floresta de abrangência mínima de gráficos esparsos". Journal of Parallel and Distributed Computing . 66 (11): 1366–1378. CiteSeerX  10.1.1.129.8991 . doi : 10.1016 / j.jpdc.2006.06.001 .
  9. ^ Karger, David R .; Klein, Philip N .; Tarjan, Robert E. (1995). "Um algoritmo de tempo linear aleatório para encontrar árvores geradoras mínimas". Jornal do ACM . 42 (2): 321–328. CiteSeerX  10.1.1.39.9012 . doi : 10.1145 / 201019.201022 .
  10. ^ Chazelle, Bernard (2000). "Um algoritmo de spanning tree mínimo com complexidade do tipo inverso de Ackermann" (PDF) . J. ACM . 47 (6): 1028–1047. CiteSeerX  10.1.1.115.2318 . doi : 10.1145 / 355541.355562 .