Lista de Alunos | Ex.5 | Ex.7

Minimum Spanning Tree

Preencher a tabela de comparação de desempenho dos algoritmos de MST. Os exemplos que precisaremos para testar a corretude dos algoritmos e o desempenho das implementações serão:

  • grafo pequeno simples
  • grafo completo com 500 nós
  • grafo intermediário com 500 nós
  • grafo que já é uma MST

Para testar a corretude precisamos retornar o número de arestas, o custo total (soma dos pesos das arestas da MST) e o número de componentes conexos. O exemplo de grafo que já é uma MST poderia ser incluido também na tabela de comparação de algoritmos para componentes conexos.

Comparação dos Resultados