Quando devo usar o Kruskal em vez de Prim (e vice-versa)?

Respostas:

199

Use o algoritmo de Prim quando você tiver um gráfico com muitas arestas.

Para um gráfico com V vértices E arestas, o algoritmo de Kruskal é executado no tempo O (E log V) e o algoritmo de Prim pode ser executado no tempo amortizado O (E + V log V) , se você usar um Fibonacci Heap .

O algoritmo de Prim é significativamente mais rápido no limite quando você tem um gráfico muito denso com muito mais arestas do que vértices. O Kruskal tem melhor desempenho em situações típicas (gráficos esparsos) porque usa estruturas de dados mais simples.

Todd Gamblin
fonte
8
Eu diria "situações típicas" em vez de média. Acho que é um termo obscuro para usar, por exemplo, qual é o "tamanho médio" de uma tabela de hash? nenhuma idéia.
Yairchu
2
@ SplittingField: Eu acredito que você está comparando maçãs e laranjas. A análise amortizada é simplesmente uma maneira de obter uma medida da função (por assim dizer) --- se é o pior caso ou o caso médio depende do que você está provando. De fato (como eu procuro agora), o artigo da wiki usa uma linguagem que implica que ela é usada apenas para análises de pior caso. Agora, usar essa análise significa que você não pode fazer promessas tão fortes sobre o custo de uma operação em particular, mas, quando o algoritmo for concluído, será realmente por O (E + VlogV), o pior caso.
agorenst 30/07/09
10
Isso parece bom em teoria, mas eu aposto que poucas pessoas podem implementar uma pilha de Fibonacci
Alexandru
2
@ tgamblin, pode haver bordas C (V, 2) na pior das hipóteses. Então, a complexidade do tempo do algoritmo de Prim não se resume a O (V ^ 2 + VlogV), ou seja, O (V ^ 2) em caso de pilha de fibonacci?
Duende verde 09/11/12
7
Há também outro fator importante: a saída do Prims é um MST apenas se o gráfico estiver conectado (a saída me parece inútil), mas a saída da Kruskal são as florestas de Abrangência Mínima (com alguma utilidade).
Andrei I
100

Encontrei um tópico muito bom na rede que explica a diferença de uma maneira muito direta: http://www.thestudentroom.co.uk/showthread.php?t=232168 .

O algoritmo de Kruskal desenvolverá uma solução a partir da borda mais barata, adicionando a próxima borda mais barata, desde que não crie um ciclo.

O algoritmo de Prim desenvolverá uma solução a partir de um vértice aleatório adicionando o próximo vértice mais barato, o vértice que não está atualmente na solução, mas conectado a ela pela aresta mais barata.

Aqui está anexada uma folha interessante sobre esse tópico.insira a descrição da imagem aquiinsira a descrição da imagem aqui

Se você implementar o Kruskal e o Prim, em sua forma ideal: com um achado de união e um monte de finbonacci, respectivamente, observará como o Kruskal é fácil de implementar em comparação com o Prim.

Prim é mais difícil com um heap de fibonacci, principalmente porque você precisa manter uma tabela de contabilidade para registrar o link bidirecional entre nós do gráfico e nós do heap. Com um Union Find, é o contrário, a estrutura é simples e pode até produzir diretamente o mst quase sem custo adicional.

Snicolas
fonte
2
Nitpick: O último 'slide' de cada um deve ser "repita até que você tenha uma árvore de abrangência"; não até o MST, que é uma tarefa recursiva - como eu sei que é mínima - é por isso que estou acompanhando Prim's / Kruskal's!
OJFord 13/06/2015
@OllieFord Encontrei este tópico por ter pesquisado uma ilustração simples dos algoritmos Prim e Kruskal. Os algoritmos garantem que você encontrará uma árvore e essa árvore é um MST. E você sabe que encontrou uma árvore quando possui exatamente as V-1 arestas.
precisa saber é o seguinte
@ mikedu95 Você está correto, fazendo o mesmo ponto que meu comentário anterior de um ângulo diferente.
OJFord
Mas não é uma pré-condição que você precise escolher apenas um peso entre os vértices, não pode escolher o peso 2 mais de uma vez no gráfico acima, você deve escolher o próximo peso ex: 3 @Snicolas
ani0904071
30

Eu sei que você não pediu isso, mas se você tiver mais unidades de processamento, sempre considere o algoritmo de Borůvka , porque ele pode ser facilmente paralelizado - portanto, ele tem uma vantagem de desempenho sobre o algoritmo Kruskal e Jarník-Prim.

malejpavouk
fonte
23

O Kruskal pode ter melhor desempenho se as arestas puderem ser classificadas em tempo linear ou se já estiverem classificadas.

Prim é melhor se o número de arestas em vértices for alto.

Daniel C. Sobral
fonte
19

Kruskal complexidade de tempo pior caso é O (E log E) , isto porque precisamos classificar as bordas. O pior caso de complexidade no horário inicial é O (E log V) com fila de prioridade ou, melhor ainda, O (E + V log V) com Fibonacci Heap . Devemos usar Kruskal quando o gráfico for esparso, com um pequeno número de arestas, como E = O (V), quando as arestas já estiverem classificadas ou se pudermos classificá-las em tempo linear. Devemos usar Prim quando o gráfico for denso, ou seja, o número de arestas é alto, como E = O (V²).

Ghiurutan Alexandru
fonte
Parece-me que Prim nunca é pior do que Kruskal em termos de velocidade. Como E deve ser pelo menos V-1, existe uma árvore de abrangência. Acho que a razão pela qual podemos preferir o Kruskal para um gráfico esparso é que sua estrutura de dados é muito simples.
Yu Gu
16

Se pararmos o algoritmo no meio, o algoritmo do prim sempre gera uma árvore conectada, mas o kruskal, por outro lado, pode gerar árvores ou florestas desconectadas

Prakhar
fonte
5

Uma aplicação importante do algoritmo de Kruskal está no cluster de link único .

Considere n vértices e você terá um gráfico completo.Para obter clusters ak desses n pontos, execute o algoritmo de Kruskal sobre as primeiras n- (k-1) arestas do conjunto de arestas classificadas. espaçamento.

Jaskaran
fonte
3

O melhor horário para Kruskal é O (E logV). Para Prim usando pilhas de fibras, podemos obter O (E + V lgV). Portanto, em um gráfico denso, o Prim é muito melhor.

Leon Stenneth
fonte
2

O Prim é melhor para gráficos mais densos, e nisso também não precisamos prestar muita atenção aos ciclos adicionando uma aresta, pois estamos lidando principalmente com nós. O Prim é mais rápido que o Kruskal no caso de gráficos complexos.

Sakshi
fonte
2

No algoritmo kruskal, temos número de arestas e número de vértices em um determinado gráfico, mas em cada aresta temos algum valor ou peso em nome do qual podemos preparar um novo gráfico que não deve ser cíclico ou não fechar de nenhum lado.

gráfico assim _____________ | | | | | | | __________ | | Dê nome a qualquer vértice a, b, c, d, e, f.

Abhishek
fonte