Lista Algoritimos e Estrutura de Dados

Prévia do material em texto

Universidade de São Paulo – USP 
Instituto de Ciências Matemáticas e de Computação – ICMC 
Departamento de Ciências de Computação – SCC 
 
SCC-503- Algoritmos e Estruturas de Dados II 
 
Responsável: Prof. Gustavo Batista 
gbatista@icmc.usp.br 
 
1. Desenhe o grafo orientado e o grafo não orientado G = (V,A) com V = {1, 2, 3, 4, 
5, 6} e A = {(1, 2), (4, 2), (5, 6), (2, 5), (3, 4)}. 
 
2. Desenhe o grafo não orientado completo com 4 vértices (K4), 5 arestas (K5) e 6 
arestas (K6). 
 
3. Quantas arestas têm um grafo não orientado completo com n vértices? E um 
grafo completo orientado? 
 
4. Implemente as operações do TAD Grafo utilizando a representação de lista de 
adjacência. 
 
5. Implemente o algoritmo de busca em profundidade utilizando as operações 
implementadas do TAD Grafo do exercício 4. 
 
6. Implemente o algoritmo para verificar se um grafo é acíclico utilizando o 
algoritmo de busca em profundidade do exercício 5. 
 
7. Mostre como a busca em profundidade funciona para o grafo a seguir. Mostre a 
sequência de vértices visitados e a árvore ou floresta de busca em profundidade. 
 
 
8. Classifique as arestas do grafo do exercício 7, segundo a busca em 
profundidade. 
 
1 2 
4 5 
7 9 8 
6 
3 
9. Altere a implementação do algoritmo de busca em profundidade para retornar 
um vetor que indique o caminho realizado pela busca. 
 
10. Mostre a ordem dos vértices produzida pela ordenação topológica do seguinte 
grafo: 
 
 
11. Mostre quais são os componentes fortemente conectados do grafo a seguir. O 
grafo é fortemente conectado? 
 
12. Mostre como a busca em largura funciona para o grafo a seguir partindo do vértice 1. 
Mostre a sequência de vértices visitados, a árvore de busca em largura e os caminhos 
mais curtos entre o vértice 1 e todos os demais vértices do grafo. 
 
 
 
1 2 
4 5 
7 9 8 
6 
3 
1 2 
4 5 
7 9 8 
6 
3 
1 2 
4 5 
7 9 8 
6 
3 
13. Explique com um exemplo, porque o algoritmo de Dijkstra não funciona corretamente 
quando existem arestas com pesos negativos. 
 
14. Mostre o funcionamento do algoritmo de Dijkstra para o seguinte grafo utilizando o 
vértice 1 como origem: 
 
 
15. Utilize o grafo abaixo para mostrar os caminhos mais curtos utilizando os algoritmos de 
Dijkstra e Floyd. 
 
 
 
16. Implemente um programa que utiliza o algoritmo de Dijkstra para solucionar o problema 
de encontrar caminhos mais curtos para um destino único. 
 
17. Um fazendeiro precisa atravessar um rio levando um lobo, uma cabra e um repolho. O 
barco disponível só tem capacidade para levar o fazendeiro acompanhado de um item. 
O fazendeiro não pode abandonar em uma das margens a cabra com o lobo nem 
mesmo o repolho com a cabra, pois o lobo comeria a cabra ou então a cabra comeria o 
repolho. Como representar cada estado? Desenhe o grafo que mostra alguma solução 
para atravessar o rio. 
 
 
1 2 
3 
4 5 
6 
1 
5 
3 
1 
2 
3 
4 
2 
2 
1 2 
4 5 
7 9 8 
6 
3 
7 
5 
11 
4 2 
20 
7 
4 
30 
3 
4 
3 50 
1