A análise da eficiência de alguns algoritmos clássicos de busca, ordenação e em gráficos

 Aula-tema: Análise de desempenho de alguns algoritmos clássicos de busca, ordenação e sobre grafos.

Essa atividade é importante para que você aprenda a representar grafos através de listas de adjacência e matriz de adjacência.

Para realizá-la, é importante seguir os passos descritos.

Ciência da Computação – 7ª Série – Análise e Complexidade de Algoritmos

Marcela Cristiani Ferreira

Pág. 5 de 8

PASSOS

Passo 1 (Equipe)

Criar um grafo com no mínimo 5 vértices, represente-o através da matriz de adjacência e através da lista de adjacência e façam um algoritmo que dê o grau de cada um de seus vértices, usando as duas maneiras representadas. Apresentar a complexidade dos algoritmos criados.

Passo 2 (Equipe)

Desenhar o grafo ponderado que representa a seguinte situação: Supor que um funcionário encarregado de verificar o estado das estradas, deseja planejar a sua rota de inspeção nas estradas que existem entre as cidades A, B, C, D e E. A rota deve se iniciar na cidade A. O custo de cada estrada é:

Estrada ligando a cidade A à cidade B = 3;

Estrada ligando a cidade A à cidade E = 12;

Estrada ligando a cidade B à cidade C = 3;

Estrada ligando a cidade B à cidade D = 2;

Estrada ligando a cidade B à cidade E = 7;

Estrada ligando a cidade C à cidade D = 2;

Estrada ligando a cidade E à cidade D = 6.

...