algoritmo de Kruskal

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

O algoritmo de Kruskal encontra uma floresta de extensão mínima de um grafo ponderado por arestas não direcionado . Se o grafo estiver conectado , ele encontra uma árvore geradora mínima . (Uma árvore geradora mínima de um grafo conectado é um subconjunto das arestas que forma uma árvore que inclui todos os vértices , onde a soma dos pesos de todas as arestas na árvore é minimizada. Para um grafo desconectado, uma floresta geradora mínima é composto por uma árvore geradora mínima para cada componente conectado .) É um algoritmo guloso na teoria dos grafospois em cada etapa ele adiciona a próxima aresta de menor peso que não formará um ciclo à floresta de extensão mínima. [1]

Este algoritmo apareceu pela primeira vez em Proceedings of the American Mathematical Society , pp. 48–50 em 1956, e foi escrito por Joseph Kruskal . [2]

Outros algoritmos para este problema incluem o algoritmo de Prim , o algoritmo de exclusão reversa e o algoritmo de Borůvka .

Algoritmo

  • crie uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore separada
  • crie um conjunto S contendo todas as arestas do grafo
  • enquanto S não é vazio e F ainda não está abrangendo
    • remover uma aresta com peso mínimo de S
    • se a aresta removida conectar duas árvores diferentes, adicione-a à floresta F , combinando duas árvores em uma única árvore

No final do algoritmo, a floresta forma uma floresta de abrangência mínima do grafo. Se o grafo estiver conectado, a floresta tem um único componente e forma uma árvore geradora mínima.

Pseudocódigo

Uma demonstração do algoritmo de Kruskal em um gráfico completo com pesos baseados na distância euclidiana.

O código a seguir é implementado com uma estrutura de dados de conjunto disjunto . Aqui, representamos nossa floresta F como um conjunto de arestas e usamos a estrutura de dados de conjuntos disjuntos para determinar com eficiência se dois vértices fazem parte da mesma árvore.

algoritmo Kruskal( G ) é
    F:= ∅
    para cada v ∈ GV faça
        MAKE-SET(v)
    para cada (u, v) em GE ordenado por peso(u, v), aumentando do 
        if FIND-SET(u) ≠ FIND-SET(v) então
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNIÃO(FIND-SET(u), FIND-SET(v))
    retornar F

Complexidade

Para um grafo com arestas E e vértices V , o algoritmo de Kruskal pode ser executado em tempo O ( E log E ), ou equivalentemente, tempo O ( E log V ), todos com estruturas de dados simples. Esses tempos de execução são equivalentes porque:

  • E é no máximoe.
  • Cada vértice isolado é um componente separado da floresta de extensão mínima. Se ignorarmos vértices isolados obtemos V ≤ 2 E , então log V é.

Podemos alcançar este limite da seguinte forma: primeiro ordenar as arestas por peso usando uma ordenação por comparação em tempo O ( E log E ); isso permite que a etapa "remover uma aresta com peso mínimo de S " funcione em tempo constante. Em seguida, usamos uma estrutura de dados de conjunto disjunto para rastrear quais vértices estão em quais componentes. Colocamos cada vértice em seu próprio conjunto disjunto, que leva operações O( V ). Finalmente, na pior das hipóteses, precisamos iterar por todas as arestas e, para cada aresta, precisamos fazer duas operações de 'localização' e possivelmente uma união. Mesmo uma estrutura de dados de conjuntos disjuntos simples, como florestas de conjuntos disjuntos com união por classificação, pode executar O( E) operações em tempo O ( E log V ). Assim, o tempo total é O ( E log E ) = O ( E log V ).

Desde que as arestas já estejam ordenadas ou possam ser ordenadas em tempo linear (por exemplo, com ordenação por contagem ou ordenação radix ), o algoritmo pode usar uma estrutura de dados disjoint-set mais sofisticada para executar em tempo O ( E α( V )) , onde α é o inverso de crescimento extremamente lento da função de Ackermann de valor único .

Exemplo

Imagem Descrição
Algoritmo Kruskal 1.svg AD e CE são as arestas mais curtas, com comprimento 5, e AD foi escolhido arbitrariamente , por isso é destacado.
Algoritmo Kruskal 2.svg CE agora é a aresta mais curta que não forma um ciclo, com comprimento 5, por isso é destacada como a segunda aresta.
Algoritmo Kruskal 3.svg A próxima aresta, DF com comprimento 6, é destacada usando praticamente o mesmo método.
Algoritmo Kruskal 4.svg As próximas arestas mais curtas são AB e BE , ambas com comprimento 7. AB é escolhido arbitrariamente e é destacado. A aresta BD foi destacada em vermelho, pois já existe um caminho (em verde) entre B e D , então formaria um ciclo ( ABD ) caso fosse escolhido.
Algoritmo Kruskal 5.svg O processo continua a destacar a próxima aresta menor, BE com comprimento 7. Muitas outras arestas são destacadas em vermelho neste estágio: BC porque formaria o laço BCE , DE porque formaria o laço DEBA e FE porque formaria formulário FEBAD .
Algoritmo Kruskal 6.svg Finalmente, o processo termina com a aresta EG de comprimento 9 e a árvore geradora mínima é encontrada.

Prova de correção

A prova consiste em duas partes. Primeiro, prova-se que o algoritmo produz uma árvore geradora . Em segundo lugar, prova-se que a árvore geradora construída é de peso mínimo.

Árvore de abrangência

Deixei seja um grafo conexo e ponderado e seja ser o subgrafo de produzido pelo algoritmo. não pode ter um ciclo, pois, por definição, uma aresta não é adicionada se resultar em um ciclo. não pode ser desconectado, pois a primeira aresta encontrada que une dois componentes de teria sido adicionado pelo algoritmo. Por isso, é uma árvore geradora de .

Minimalidade

Mostramos que a seguinte proposição P é verdadeira por indução : Se F é o conjunto de arestas escolhidas em qualquer estágio do algoritmo, então existe alguma árvore geradora mínima que contém F e nenhuma das arestas rejeitadas pelo algoritmo.

  • Claramente P é verdadeiro no início, quando F está vazio: qualquer árvore geradora mínima serve, e existe uma porque um grafo conectado ponderado sempre tem uma árvore geradora mínima.
  • Agora suponha que P é verdadeiro para algum conjunto de arestas não final F e seja T uma árvore geradora mínima que contém F .
    • Se a próxima aresta escolhida e também estiver em T , então P é verdadeiro para F + e .
    • Caso contrário, se e não está em T então T + e tem um ciclo C . Este ciclo contém arestas que não pertencem a F , pois e não forma um ciclo quando adicionado a F , mas sim em T. Seja f uma aresta que está em C mas não em F + e . Note que f também pertence a T , e por P não foi considerado pelo algoritmo. f deve, portanto, ter um peso pelo menos tão grande quanto e . Então Tf + e é uma árvore e tem o mesmo ou menor peso que T . Então Tf + e é uma árvore geradora mínima contendo F + e e novamente P é válido.
  • Portanto, pelo princípio da indução, P vale quando F se torna uma árvore geradora, o que só é possível se F for uma árvore geradora mínima.

Algoritmo paralelo

O algoritmo de Kruskal é inerentemente sequencial e difícil de paralelizar. É, no entanto, possível realizar a ordenação inicial das arestas em paralelo ou, alternativamente, usar uma implementação paralela de um heap binário para extrair a aresta de peso mínimo em cada iteração. [3] Como a classificação paralela é possível no temposobreprocessadores, [4] o tempo de execução do algoritmo de Kruskal pode ser reduzido para O ( E α( V )), onde α novamente é o inverso da função de Ackermann de valor único .

Uma variante do algoritmo de Kruskal, denominada Filter-Kruskal, foi descrita por Osipov et al. [5] e é mais adequado para paralelização. A ideia básica por trás do Filter-Kruskal é particionar as arestas de maneira semelhante ao quicksort e filtrar arestas que conectam vértices da mesma árvore para reduzir o custo de ordenação. O pseudocódigo a seguir demonstra isso.

função filter_kruskal(G) é 
    se |GE| < kruskal_threshold:
         retorna kruskal(G)
    pivô = escolha_aleatório(GE)
    ,= partição(GE, pivô)
    A = filter_kruskal()
    = filtro()
    A = A ∪ filter_kruskal()
     retornar A

partição de função (E, pivô) é
     = ∅, = ∅
     foreach (u, v) em E faça 
        se peso(u, v) <= pivô então
             = ∪ {(u, v)}
         senão
             = ∪ {(u, v)}
     retorno ,

função filtro (E) é
    = ∅
     foreach (u, v) em E faça 
        se find_set(u) ≠ find_set(v) então
             = ∪ {(u, v)}
     retorno 

O Filter-Kruskal se presta melhor para paralelização, pois ordenação, filtragem e particionamento podem ser facilmente executados em paralelo, distribuindo as bordas entre os processadores. [5]

Finalmente, outras variantes de uma implementação paralela do algoritmo de Kruskal foram exploradas. Exemplos incluem um esquema que usa threads auxiliares para remover arestas que definitivamente não fazem parte do MST em segundo plano, [6] e uma variante que executa o algoritmo sequencial em p subgrafos, então mescla esses subgrafos até que apenas um, o MST final, restos. [7]

Veja também

Referências

  1. ^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein (2009). Introdução aos algoritmos (terceira ed.). Imprensa do MIT. pág.  631 . ISBN 978-0262258104.{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. ^ Kruskal, JB (1956). "Na subárvore mais curta de um grafo e o problema do caixeiro viajante" . Anais da American Mathematical Society . 7 (1): 48–50. doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241 . 
  3. ^ Quinn, Michael J.; Deo, Narsingh (1984). "Algoritmos de grafos paralelos". Pesquisas de Computação ACM . 16 (3): 319–348. doi : 10.1145/2514.2515 . S2CID 6833839 . 
  4. ^ Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003). Introdução à Computação Paralela . págs. 412-413. ISBN 978-0201648652.
  5. ^ a b Osipov, Vitaly; Sanders, Pedro; Singler, Johannes (2009). "O algoritmo de árvore geradora mínima de filtro-kruskal" (PDF) . Anais do XI Workshop de Engenharia de Algoritmos e Experimentos (ALENEX). Sociedade de Matemática Industrial e Aplicada : 52–61.
  6. ^ Katsigiannis, Anastasios; Anastopoulos, Nikos; Konstantinos, Nikas; Koziris, Nectários (2012). "Uma abordagem para paralelizar o algoritmo de Kruskal usando threads auxiliares" (PDF) . Workshops de Simpósio de Processamento Paralelo e Distribuído e Fórum de Doutorado (IPDPSW), 2012 IEEE 26th International : 1601–1610. doi : 10.1109/IPDPSW.2012.201 . ISBN  978-1-4673-0974-5. S2CID  14430930 .
  7. ^ Lončar, Vladimir; Škrbić, Srdjan; Balaž, Antun (2014). "Paralelização de algoritmos de árvore geradora mínima usando arquiteturas de memória distribuída" . Transações em Tecnologias de Engenharia. : 543-554. doi : 10.1007/978-94-017-8832-8_39 . ISBN 978-94-017-8831-1.

Links externos