O conteúdo da prova será tudo que vimos nas aulas 9 a 16 e estruturas
de dados básicas para grafos e digrafos que temos usado:
- Conceitos básicos:
- Digrafos
- Grafos
- Estruturas de dados
- Matriz de adjacência
- Vetor de listas de adjacência
- Busca em profundidade
- Componentes de grafos
- Aplicações
- Grafos bipartidos e ciclos ímpares
- Pontes em grafos
- Articulações em grafos
- Componentes fortemente conexos
- Busca em largura
- Busca em largura
- Caminhos mínimos
- Potenciais e caminhos de custo mínimo
- Grafos e digrafos com custos
- Custos nos arcos
- Caminhos de custo mínimo
- Caminhos de custo mínimo
- Algoritmo de Dijkstra
- Algoritmo de Dijkstra para grafos densos e esparsos
- Caminhos mínimos em DAGs
- Algoritmo de Bellman-Ford