Algoritmo de Kruskal - Kruskal's algorithm

O algoritmo de Kruskal encontra uma floresta de abrangência mínima de um gráfico não direcionado com aresta ponderada . Se o gráfico estiver conectado , ele encontra uma árvore de abrangência 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 da árvore é minimizada. Para um grafo desconectado, uma floresta geradora mínima é composto de uma árvore geradora mínima para cada componente conectado .) É um algoritmo ganancioso na teoria dos grafos, pois em cada etapa adiciona a próxima aresta de menor peso que não formará um ciclo para a floresta geradora mínima.

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

Outros algoritmos para este problema incluem o algoritmo de Prim , o algoritmo reverso-delete , e algoritmo de borůvka .

Algoritmo

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

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

Pseudo-có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 separado . 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.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Complexidade

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

• E é no máximo e . ${\ displaystyle V ^ {2}}$${\ displaystyle \ log V ^ {2} = 2 \ log V \ in O (\ log V)}$
• Cada vértice isolado é um componente separado da floresta de abrangência mínima. Se ignorarmos vértices isolados, obtemos V ≤ 2 E , então log V é . ${\ displaystyle O (\ log E)}$

Podemos atingir esse limite da seguinte maneira: primeiro classifique as arestas por peso usando uma classificação por comparação em tempo O ( E log E ); isso permite que a etapa "remova uma aresta com peso mínimo de S " para operar em tempo constante. Em seguida, usamos uma estrutura de dados com conjuntos separados para controlar 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, no pior caso, 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 simples de dados disjuntos-conjunto, tais como florestas disjuntos-conjunto com união por classificação pode executar O ( E operações) em S ( E log V ) vez. Assim, o tempo total é O ( E log E ) = O ( E log V ).

Desde que as arestas já estejam classificadas ou possam ser classificadas em tempo linear (por exemplo, com classificação de contagem ou classificação de raiz ), o algoritmo pode usar uma estrutura de dados de conjunto disjunto 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
	AD e CE são as arestas mais curtas, com comprimento 5, e AD foi escolhida arbitrariamente , por isso é destacada.
	CE agora é a aresta mais curta que não forma um ciclo, com comprimento 5, por isso é destacada como a segunda aresta.
	A próxima aresta, DF com comprimento 6, é destacada usando praticamente o mesmo método.
	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 ela formaria um ciclo ( ABD ) se fosse escolhida.
	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 loop BCE , DE porque formaria o loop DEBA e FE porque faria formulário FEBAD .
	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, é provado que o algoritmo produz uma árvore geradora . Em segundo lugar, está provado que a árvore geradora construída tem peso mínimo.

Spanning tree

Seja um gráfico conectado e ponderado e seja o subgrafo 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 adicionada pelo algoritmo. Portanto, é uma árvore abrangente de . ${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle G}$

Minimalidade

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

• Claramente P é verdadeiro no início, quando F está vazio: qualquer árvore geradora mínima servirá, e existe uma porque um grafo conectado ponderado sempre tem uma árvore geradora mínima.
• Agora vamos supor P é verdade para alguns set borda não final F e deixá- T ser uma árvore de cobertura 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 .
  • De outro modo, se e não é em T , em seguida, t + e tem um ciclo de C . Este ciclo contém arestas que não pertencem a F , uma vez que e não formam um ciclo, quando adicionado a F , mas faz em T . Seja f uma aresta que está em C, mas não em F + e . Observe 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 T - f + e é uma árvore, e tem o mesmo ou menos peso, como T . Portanto, T - f + e é uma árvore geradora mínima contendo F + e e novamente P é válido.
• Portanto, pelo princípio da indução, P é válido quando F se tornou uma árvore geradora, o que só é possível se F for ela própria uma árvore geradora mínima.

Algoritmo paralelo

O algoritmo de Kruskal é inerentemente sequencial e difícil de paralelizar. No entanto, é possível realizar a classificaçã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. Como a classificação paralela é possível no tempo nos processadores, 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 . ${\ displaystyle O (n)}$${\ displaystyle O (\ log n)}$

Uma variante do algoritmo de Kruskal, chamada Filter-Kruskal, foi descrita por Osipov et al. 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 as arestas que conectam os vértices da mesma árvore para reduzir o custo de classificação. O pseudocódigo a seguir demonstra isso.

function filter_kruskal(G) is
    if |G.E| < kruskal_threshold:
        return kruskal(G)
    pivot = choose_random(G.E)
    ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$ = partition(G.E, pivot)
    A = filter_kruskal(${\displaystyle E_{\leq }}$)
    ${\displaystyle E_{>}}$ = filter(${\displaystyle E_{>}}$)
    A = A ∪ filter_kruskal(${\displaystyle E_{>}}$)
    return A

function partition(E, pivot) is
    ${\displaystyle E_{\leq }}$ = ∅, ${\displaystyle E_{>}}$ = ∅
    foreach (u, v) in E do
        if weight(u, v) <= pivot then
            ${\displaystyle E_{\leq }}$ = ${\displaystyle E_{\leq }}$ ∪ {(u, v)}
        else
            ${\displaystyle E_{>}}$ = ${\displaystyle E_{>}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$

function filter(E) is
    ${\displaystyle E_{\text{filtered}}}$ = ∅
    foreach (u, v) in E do
        if find_set(u) ≠ find_set(v) then
            ${\displaystyle E_{\text{filtered}}}$ = ${\displaystyle E_{\text{filtered}}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\text{filtered}}}$

O Filter-Kruskal se presta melhor à paralelização, pois a classificação, filtragem e particionamento podem ser facilmente executados em paralelo, distribuindo as bordas entre os processadores.

Finalmente, outras variantes de uma implementação paralela do algoritmo de Kruskal foram exploradas. Os exemplos incluem um esquema que usa threads auxiliares para remover arestas que definitivamente não fazem parte do MST no fundo e uma variante que executa o algoritmo sequencial em p subgráficos e, em seguida, mescla esses subgráficos até que apenas um, o MST final, permaneça.

Veja também

• Algoritmo de Prim
• Algoritmo de Dijkstra
• Algoritmo de Borůvka
• Algoritmo de exclusão reversa
• Clustering de ligação única
• Chave geométrica gananciosa

Referências

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN   0-262-03293-7 . Seção 23.2: Os algoritmos de Kruskal e Prim, pp. 567–574.
• Michael T. Goodrich e Roberto Tamassia . Estruturas de dados e algoritmos em Java , quarta edição. John Wiley & Sons, Inc., 2006. ISBN   0-471-73884-0 . Seção 13.7.1: Algoritmo de Kruskal, pp. 632 ..

links externos

• Dados para o exemplo do artigo .
• Plugin Gephi para calcular o código-fonte de uma árvore de abrangência mínima .
• Algoritmo de Kruskal com exemplo e programa em c ++
• Código do algoritmo de Kruskal em C ++ aplicado a números aleatórios
• Código do algoritmo de Kruskal em Python com explicação