UFSC - CTC - INE
INE5413 - GRAFOS
Turma: 09238B (SIN)

CONTEÚDO DOS SLIDES E PROGRAMAS VISTOS EM AULA (2023.1) - ver moodle

0) APRESENTAÇÃO

• 0.0) Apresentação do curso
• 0.1) Introdução a Linux / C++

1) INTRODUÇÃO

• 1.1) Conceitos básicos (terminologia, caminhos e ciclos)
• 1.2) Representações computacionais de grafos

2) BUSCA EM PROFUNDIDADE

• 2.1) Algoritmo Depth-First Search (DFS)
• 2.2) Aplicações da DFS
• 2.3) Problemas envolvendo o uso de DFS

3) BUSCA EM LARGURA

• 3.1) Algoritmo Breadth-First Search (BFS) e Caminhos mínimos
• 3.2) Problemas envolvendo o uso de BFS

4) ÁRVORES GERADORAS DE CUSTO MÍNIMO (MSTs)

• 4.0) Introdução
• 4.1) Algoritmo guloso geral
• 4.2) Algoritmo de Kruskal
• 4.3) Algoritmo de Prim

5) GRAFOS DIRIGIDOS

• 5.1) Introdução
• 5.2) API para digrafo
• 5.3) Buscas em digrafos
• 5.4) Ordenamento topológico
• 5.5) Conectividade forte

6) CAMINHOS DE CUSTO MÍNIMO COM ORIGEM ÚNICA

• 6.1) Algoritmo de Dijkstra
• 6.2) Algoritmo de Bellman-Ford

7) CAMINHOS DE CUSTO MÍNIMO ENTRE TODOS OS PARES DE VÉRTICES

• 7.1) Algoritmo de Floyd-Warshall