Há cerca de um ano, um amigo e eu pensamos em uma maneira de implementar o algoritmo de Kruskal para gráficos densos melhor do que o usual vinculado (sem assumir arestas pré-classificadas). Especificamente, atingimos Θ ( n 2 ) em todos os casos, semelhante ao Prim quando implementado usando matrizes de adjacência.
Publiquei um pouco sobre o algoritmo em meu blog , incluindo códigos e benchmarks C ++, mas aqui está a ideia geral:
Mantenha um nó representativo para cada componente conectado. Inicialmente, todos os nós se representam.
Mantenha um vetor
dist[i]
que, para cada componentei
, tenha o menor incidente na borda de cruzamento de componentesi
.Ao encontrar a aresta mais leve que atravessa as partições, basta descobrir
i
que minimiza o peso dedist[i]
, em tempo linear.Ao unir dois componentes e c j , modifique a matriz de adjacência A , de modo que agora A i , k = min { A i , k , A j , k } para todos os componentes k , e marque i como não mais representativo de sua componente conectado (apenas j permanecerá agora).
A contração da borda mais leve e a descoberta da referida borda podem, assim, ser feitas em tempo linear. Fazemos isso vezes para encontrar o MST. É necessária uma pequena contabilidade para descobrir qual borda queremos adicionar ao MST, mas não aumenta a complexidade. Assim, o tempo de execução é Θ ( n 2 ) . A implementação é apenas um par de loops.
Esta versão do Kruskal é bem conhecida na literatura?
fonte