Arvore-Geradora-Minima

Implementação e análise de tempo dos algoritmo de Kruskal e Prim com auxilio da biblioteca Networkx

Roteiro da atividade:

Utilizando uma biblioteca de grafos:

• Crie um grafo aleatório com o número de vértices (n) e o número de arestas (m) arbitrários.

• Visualize o grafo criado com auxílio da biblioteca.

• Execute o algoritmo de Prim e Kruskall no grafo gerado.

• Visualize a árvore geradora mínima calculada utilizando duas estratégias:

  1. Omitindo as arestas ausentes;

  2. Colorindo as arestas ausentes de uma cor diferente.

• Gere grafos aleatórios variando os valores de n e m.

• Observe o tempo de execução dos algoritmos de Prim e Kruskall para os grafos gerados (construa um gráfico para facilitar a observação).

• Discuta os tempos observados.