Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Otimização em Redes Professor: Marco Antonio M. Carvalho Lista de Exercícios 02 1. Para o grafo da figura abaixo, apresente a sequência de vertices após a aplicação da BFS e da
DFS a partir do vértice 7, bem como a classificação das arestas e a árvore de profundidade.
Considere a representação por listas de adjacências em ordem lexicográfica.
2. Para o grafo da figura abaixo, apresente a sequência de vertices após a aplicação da DFS a partir
do vértice 7, bem como a classificação das arestas e árvore de profundidade. Considere a
representação por listas de adjacências em ordem lexicográfica.
3. Execute o algoritmo de Tarjan para os grafos abaixo, classificando as arestas e também
apresentando as componentes fortemente conexas e os vértices e arestas de articulação.
4. Apresente duas implementações para a busca em profundidade: uma utilizando representação por
matrizes de adjacências e outra utilizando representação por lista de adjacências.
5. Execute o algoritmo de Bellman-Ford para o grafo abaixo.
6. Execute o algoritmo de Dijkstra para o grafo abaixo, tendo como vértice inicial o vértice s.
7. Execute os algoritmos de Bellman-Ford, Floyd-Warshall, Johnson para os grafos abaixo. 8. Execute o algoritmo A* para determinar os caminhos mais curtos entre os pares de vértices
elencados abaixo, usando como heurística a distância em linha reta a. Urziceni e Bucharest; b. Zerind e Bucharest; c. Dobreta e Bucharest.